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

zbMATH Keywords

LogicFormal languages.Regular tree languagesTree-walking automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1670851
• 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

• 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?)
• scientific article; zbMATH DE number 1408335 (Why is no real title available?)
• 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
• Parallel and two-way automata on directed ordered acyclic graphs
• Translations on a context free grammar

Cited in

(11)

• Tree-walking automata do not recognize all regular languages
• Pebble weighted automata and weighted logics
• Deciding twig-definability of node selecting tree automata
• Deciding determinism of caterpillar expressions
• Regular languages with variables on graphs
• scientific article; zbMATH DE number 1773074 (Why is no real title available?)
• Automata for XML -- a survey
• scientific article; zbMATH DE number 1670851 (Why is no real title available?)
• Loops and overloops for tree walking automata
• Deterministic Caterpillar Expressions
• Transitive closure logic, nested tree walking automata, and XPath

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)