A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra

MaRDI QIDQ5207048zbMATH OpenFDO

Authors Mikołaj Bojańczyk, Bartek Klin

Publication date 3 January 2020

Full work available at URL https://arxiv.org/abs/1804.06667

zbMATH Keywords

infinite treealgebraic language theory\(\omega\)-clone

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70)

Recommendations

• Recognisability for algebras of infinite trees
• scientific article; zbMATH DE number 5872386
• Algebraic recognizability of regular tree languages
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• An algebraic proof of Rabin's tree theorem

Cites work

• scientific article; zbMATH DE number 176766 (Why is no real title available?)
• scientific article; zbMATH DE number 1216133 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 2222246 (Why is no real title available?)
• Algebra for Infinite Forests with an Application to the Temporal Logic EF
• An algebraic proof of Rabin's tree theorem
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• Definability equals recognizability for graphs of bounded treewidth
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Regular languages of thin trees
• Regular languages of words over countable linear orderings
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic theory of order

Cited in

(4)

• Recognisability for algebras of infinite trees
• Monadic monadic second order logic
• scientific article; zbMATH DE number 7350772 (Why is no real title available?)
• Solvability of orbit-finite systems of linear equations

This page was built for publication: A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207048)