Tree-walking automata cannot be determinized

DOI10.1016/j.tcs.2005.10.031zbMath1086.68070OpenAlexW2030011197WikidataQ56768686 ScholiaQ56768686MaRDI QIDQ817841

Mikołaj Bojańczyk, Thomas Colcombet

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.031

zbMATH Keywords

tree-walking automatadeterministic tree-walking automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Deciding determinism of caterpillar expressions ⋮ Homomorphisms on graph-walking automata ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Tree-walking-storage automata ⋮ Deterministic Caterpillar Expressions ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs ⋮ Loops and overloops for tree-walking automata ⋮ Reversibility of computations in graph-walking automata ⋮ Walking on data words ⋮ Loops and Overloops for Tree Walking Automata ⋮ Automata on finite trees ⋮ Algebra for trees

Cites Work

• Parallel and two-way automata on directed ordered acyclic graphs
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Translations on a context free grammar
• Unnamed Item
• Unnamed Item
• Unnamed Item