Mikołaj Bojańczyk, Tomasz Idziaszek
Algebra for Infinite Forests with an Application to the Temporal Logic EF. CONCUR, 2009 PDF
Mikołaj Bojańczyk, Filippo Cavallari, Thomas Place, Michal Skrzypczak
Regular tree languages in low levels of the Wadge Hierarchy. Log. Methods Comput. Sci., 2019 PDF
Tomasz Idziaszek, Michal Skrzypczak, Mikołaj Bojańczyk
Regular Languages of Thin Trees. Theory Comput. Syst., 2016 PDF
Mikołaj Bojańczyk, Bartek Klin
A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra. Log. Methods Comput. Sci., 2019 PDF
There are algebras for finite words (monoids or semigroups), infinite words (e.g. ω-semigroups or Wilke semigroups) and finite trees (e.g. clones or forest algebras). What about infinite trees? In [1] we propose a notion of algebra for infinite trees, which is an extension of forest algebra. It is not completely satisfactory (there is no result that finite algebras can be represented in a finite way), but it is good enough to characterize some logics, e.g. the temporal logic EF. Paper [2], which is the journal version of an ICALP 2012 paper, continues the study of algebras for infinite trees, by giving a structural characterization of some random logic (namely, Boolean combinations of sets that are open in the Borel topology). The idea is to learn what kind of structural theory of regular tree languages is needed to do nontrivial characterizations. Paper [3], which is the journal version of a STACS 2013 paper, shows that most of the technical problems go away when considering thin trees, which are infinite trees with countably many branches. Paper [4] gives a counterexample of sorts – it shows a language of infinite trees which is not regular, but where a natural Myhill-Nerode equivalence has finite index.
Leave a Reply