Complementing deterministic tree-walking automata

DOI10.1016/J.IPL.2005.09.017MaRDI QIDQ845667zbMATH OpenOpenAlexFDO

Authors Anca Muscholl, Mathias Samuelides, Luc Segoufin

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

formal languagescombinatorial problemstree-automata

Mathematics Subject Classification ID

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

Recommendations

• Weighted tree-walking automata
• scientific article; zbMATH DE number 897895
• scientific article; zbMATH DE number 480522
• Tree-walking-storage automata
• Completeness of tree automata completion
• Tree automata
• scientific article
• scientific article; zbMATH DE number 1670851
• On the Determinization of Weighted Finite Automata
• scientific article; zbMATH DE number 7362732

Cites work

• scientific article; zbMATH DE number 1408335 (Why is no real title available?)
• Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
• Automata, Languages and Programming
• Complexity results for two-way and multi-pebble automata and their logics
• Translations on a context free grammar
• Tree-walking automata do not recognize all regular languages
• Typechecking for XML transformers

Cited in

(16)

• Reversibility of computations in graph-walking automata
• Expressive Power of Pebble Automata
• State complexity of transforming graph-walking automata to halting, returning and reversible
• Automata on finite trees
• On multi-head automata with restricted nondeterminism
• Loops and overloops for tree-walking automata
• Complexity of Pebble Tree-Walking Automata
• scientific article; zbMATH DE number 1408335 (Why is no real title available?)
• Homomorphisms and inverse homomorphisms on graph-walking automata
• Tree-walking automata cannot be determinized
• Two-way pebble transducers for partial functions and their composition
• A time to cast away stones
• Loops and overloops for tree walking automata
• Pebble alternating tree-walking automata and their recognizing power
• XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
• State complexity of union and intersection on graph-walking automata

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

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