Bojańczyk, Mikołaj and Klin, Bartek - A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra

lmcs:4447 - Logical Methods in Computer Science, November 29, 2019, Volume 15, Issue 4
A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra

Authors: Bojańczyk, Mikołaj and Klin, Bartek

$\omega$-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as $\omega$-semigroups are convenient algebras for infinite words. In the algebraic theory of languages, one hopes that a language is regular if and only if it is recognized by an algebra that is finite in some simple sense. We show that, for infinite trees, the situation is not so simple: there exists an $\omega$-clone that is finite on every sort and finitely generated, but recognizes a non-regular language.


Source : oai:arXiv.org:1804.06667
Volume: Volume 15, Issue 4
Published on: November 29, 2019
Submitted on: April 19, 2018
Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3,F.4.3


Share