Tree-walking automata cannot be determinized

DOI10.1016/J.TCS.2005.10.031zbMATH Open1086.68070OpenAlexW2030011197WikidataQ56768686 ScholiaQ56768686MaRDI QIDQ817841FDOQ817841

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Translations on a context free grammar
• Parallel and two-way automata on directed ordered acyclic graphs
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

Cited In (15)

• Reversibility of computations in graph-walking automata
• 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
• Loops and Overloops for Tree Walking Automata
• 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
• 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)