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)

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

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)