Tree-walking automata cannot be determinized
From MaRDI portal
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
- scientific article; zbMATH DE number 1670851 (Why is no real title available?)
- scientific article; zbMATH DE number 1354852 (Why is no real title available?)
- scientific article; zbMATH DE number 1408335 (Why is no real title available?)
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Parallel and two-way automata on directed ordered acyclic graphs
- Translations on a context free grammar
Cited in
(17)- Deterministic Caterpillar Expressions
- 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
- Loops and overloops for tree walking automata
- Theoretical computer science: computational complexity
- Algebra for trees
- Loops and overloops for tree-walking automata
- Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
- It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
- Homomorphisms and inverse homomorphisms on graph-walking automata
- Automata on finite trees
- Tree-walking-storage automata
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Walking on data words
- Homomorphisms on graph-walking automata
- Deciding determinism of 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)
