Tree-walking automata cannot be determinized
From MaRDI portal
Publication:817841
DOI10.1016/J.TCS.2005.10.031zbMATH Open1086.68070OpenAlexW2030011197WikidataQ56768686 ScholiaQ56768686MaRDI QIDQ817841FDOQ817841
Authors: 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
Recommendations
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Tree-walking automata do not recognize all regular languages
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
- Complementing deterministic tree-walking automata
Cites Work
Cited In (17)
- Reversibility of computations in graph-walking automata
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Tree-walking automata do not recognize all regular languages
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Deciding determinism of caterpillar expressions
- Automata on finite trees
- It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
- Theoretical computer science: computational complexity
- Loops and overloops for tree-walking automata
- Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
- Homomorphisms and inverse homomorphisms on graph-walking automata
- Tree-walking-storage automata
- Homomorphisms on graph-walking automata
- Loops and overloops for tree walking automata
- Algebra for trees
- Walking on data words
- Deterministic Caterpillar Expressions
This page was built for publication: Tree-walking automata cannot be determinized
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817841)
