Complementing deterministic tree-walking automata

DOI10.1016/j.ipl.2005.09.017zbMath1184.68324OpenAlexW2012346719MaRDI QIDQ845667

Luc Segoufin, Anca Muscholl, Mathias Samuelides

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.09.017

zbMATH Keywords

combinatorial problemsformal languagestree-automata

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Formal languages and automata (68Q45)

Related Items (9)

Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ A time to cast away stones ⋮ On multi-head automata with restricted nondeterminism ⋮ Reversibility of computations in graph-walking automata ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Two-way pebble transducers for partial functions and their composition ⋮ Automata on finite trees ⋮ State complexity of union and intersection on graph-walking automata

Cites Work

• Unnamed Item
• Complexity results for two-way and multi-pebble automata and their logics
• Typechecking for XML transformers
• Tree-walking automata do not recognize all regular languages
• Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
• Automata, Languages and Programming
• Translations on a context free grammar

This page was built for publication: Complementing deterministic tree-walking automata