Opendata, web and dolomites


A unified theory of finite-state recognisability

Total Cost €


EC-Contrib. €






Project "LIPA" data sheet

The following table provides information about the project.


Organization address
postcode: 00 927

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Poland [PL]
 Project website
 Total cost 1˙768˙125 €
 EC max contribution 1˙768˙125 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2015-CoG
 Funding Scheme ERC-COG
 Starting year 2016
 Duration (year-month-day) from 2016-05-01   to  2021-04-30


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    UNIWERSYTET WARSZAWSKI PL (WARSZAWA) coordinator 1˙768˙125.00


 Project objective

Finite-state devices like finite automata and monoids on finite words, or extensions to trees and infinite objects, are fundamental tools of logic in computer science. There are tens of models in the literature, ranging from finite automata on finite words to weighted automata on infinite trees. Many existing finite-state models share important similarities, like existence of canonical (minimal) devices, or decidability of emptiness, or a logic-automata connection. The first and primary goal of this project is to systematically investigate these similarities, and create a unified theory of finite-state devices, which:

1. covers the whole spectrum of existing finite-state devices, including settings with diverse inputs (e.g. words and trees, or infinite inputs, or infinite alphabets) and diverse outputs (e.g. Boolean like in the classical automata, or numbers like in weighted automata); and

2. sheds light on the correct notion of finite-state device in settings where there is no universally accepted choice or where finite-state devices have not been considered at all.

The theory of finite-state devices is one of those fields of theory where even the more advanced results have natural potential for applications. It is surprising and sad how little of this potential is normally realised, with most existing software using only the most rudimentary theoretical techniques. The second goal of the project is to create two tools which use more advanced aspects of the theory of automata to solve simple problems of wide applicability (i.e. at least tens of thousands of users):

1. a system that automatically grades exercises in automata, which goes beyond simple testing, and forces the students to write proofs

2. a system that uses learning to synthesise text transformations (such a search-and-replace, but also more powerful ones) by using examples


year authors and title journal last update
List of publications.
2017 Bojanczyk, Mikolaj ; Pilipczuk, Michal
Optimizing Tree Decompositions in MSO
published pages: , ISSN: , DOI: 10.4230/LIPIcs.STACS.2017.15
STACS 2020-04-23
2017 Mikołaj Bojańczyk
It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
published pages: 37-46, ISSN: 0169-2968, DOI: 10.3233/FI-2017-1551
Fundamenta Informaticae 154/1-4 2020-04-23
2017 Laure Daviaud, Ismaël Jecker, Pierre-Alain Reynier, Didier Villevalois
Degree of Sequentiality of Weighted Automata
published pages: 215-230, ISSN: , DOI: 10.1007/978-3-662-54458-7_13
FoSSaCS 2020-04-23
2017 Bojanczyk, Mikolaj ; Gimbert, Hugo ; Kelmendi, Edon
Emptiness of Zero Automata Is Decidable
published pages: , ISSN: , DOI: 10.4230/LIPIcs.ICALP.2017.106
ICALP 2020-04-23
2017 Laure Daviaud, Marianne Johnson
The Shortest Identities for Max-Plus Automata with Two States
published pages: , ISSN: , DOI: 10.4230/LIPIcs.MFCS.2017.48
MFCS 2020-04-23
2017 Laure Daviaud, Guillon, Pierre ; Merlet, Glenn
Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices
published pages: , ISSN: , DOI: 10.4230/LIPIcs.MFCS.2017.19
MFCS 2020-04-23
2017 Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle
Which Classes of Origin Graphs Are Generated by Transducers
published pages: , ISSN: , DOI: 10.4230/LIPIcs.ICALP.2017.114
ICALP 2020-04-23
2017 Mikołaj Bojańczyk, Henryk Michalewski
Some connections between universal algebra and logics for trees
published pages: , ISSN: , DOI:
2016 Mikołaj Bojańczyk
Thin MSO with a Probabilistic Path Quantifier
published pages: , ISSN: , DOI: 10.4230/LIPIcs.ICALP.2016.96
2018 Mikołaj Bojańczyk
Two monads for graphs
published pages: , ISSN: , DOI:
2018 Mikołaj Bojańczyk, Bartek Klin
A non-regular language of infinite trees that is recognizable by a finite algebra
published pages: , ISSN: , DOI:
2018 Mikołaj Bojańczyk
Polyregular Functions
published pages: , ISSN: , DOI:

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "LIPA" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "LIPA" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

DimorphicCircuits (2019)

Elucidating the development of sexually-dimorphic circuits: from molecular mechanisms to synapses and behavior

Read More  

SUExp (2018)

Strategic Uncertainty: An Experimental Investigation

Read More  

NanoPD_P (2020)

High throughput multiplexed trace-analyte screening for diagnostics applications

Read More