Nondeterministic tree-walking automata are not closed under complementation

DOI10.4230/LIPICS.ICALP.2025.168MaRDI QIDQ7397629zbMATH OpenFDO

Authors Olga Martynova, Alexander Okhotin

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.168

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
• Complementing deterministic tree-walking automata
• Complexity of Pebble Tree-Walking Automata
• Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
• Expressive Power of Pebble Automata
• Halting space-bounded computations
• scientific article; zbMATH DE number 1110839 (Why is no real title available?)
• scientific article; zbMATH DE number 1948151 (Why is no real title available?)
• scientific article; zbMATH DE number 1408335 (Why is no real title available?)
• It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
• Lower bounds for unambiguous automata via communication complexity
• On complementing unambiguous automata and graphs with many cliques and cocliques
• On the power of tree-walking automata.
• Reversibility of computations in graph-walking automata
• Translations on a context free grammar
• Tree-Walking Automata
• Tree-walking automata cannot be determinized
• Tree-Walking Automata Do Not Recognize All Regular Languages
• Unambiguity in automata theory

This page was built for publication: Nondeterministic tree-walking automata are not closed under complementation

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