Tree-walking automata do not recognize all regular languages

DOI10.1145/1060590.1060626MaRDI QIDQ3581424zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk, Thomas Colcombet

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060626

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Tree-Walking Automata Do Not Recognize All Regular Languages
• Tree-walking automata cannot be determinized
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 1670851
• On the power of tree-walking automata.

Cited in

(14)

• Tree-Walking Automata Do Not Recognize All Regular Languages
• Automata for XML -- a survey
• It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
• Streaming tree automata
• scientific article; zbMATH DE number 1670851 (Why is no real title available?)
• An automata-theoretic approach to infinite-state systems
• Loops and overloops for tree-walking automata
• On the power of tree-walking automata.
• Complementing deterministic tree-walking automata
• scientific article; zbMATH DE number 1408335 (Why is no real title available?)
• Tree-walking automata cannot be determinized
• Loops and overloops for tree walking automata
• Pebble alternating tree-walking automata and their recognizing power
• Deterministic Caterpillar Expressions

This page was built for publication: Tree-walking automata do not recognize all regular languages

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