On the power of tree-walking automata.

DOI10.1016/S0890-5401(03)00013-0MaRDI QIDQ1401944zbMATH OpenOpenAlexFDO

Authors Frank Neven, Thomas Schwentick

Publication date 19 August 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0890-5401(03)00013-0, http://hdl.handle.net/1942/617

zbMATH Keywords

Formal languages.LogicRegular tree languagesTree-walking automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the power of tree-walking automata
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Tree-walking automata do not recognize all regular languages
• Loops and overloops for tree-walking automata
• Loops and overloops for tree walking automata

Cites work

• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• A formal model for an expressive fragment of XSLT
• Descriptive complexity: a logician's approach to computation.
• Domains of partial attributed tree transducers
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 408785 (Why is no real title available?)
• scientific article; zbMATH DE number 1354852 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Parallel and two-way automata on directed ordered acyclic graphs
• Translations on a context free grammar
• Tree-walking pebble automata

Cited in

(12)

• Deciding twig-definability of node selecting tree automata
• On the power of tree-walking automata
• Deterministic Caterpillar Expressions
• Transitive closure logic, nested tree walking automata, and XPath
• Tree-walking automata do not recognize all regular languages
• Regular languages with variables on graphs
• Regularly extended two-way nondeterministic tree automata
• Pebble weighted automata and weighted logics
• Loops and overloops for tree walking automata
• Nondeterministic tree-walking automata are not closed under complementation
• Deciding determinism of caterpillar expressions
• Automata for XML -- a survey

This page was built for publication: On the power of tree-walking automata.

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