Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure

DOI10.2168/LMCS-3(2:3)2007MaRDI QIDQ5310688zbMATH OpenFDO

Authors Hendrik Jan Hoogeboom, Joost Engelfriet

Publication date 11 October 2007

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/LMCS-3(2:3)2007

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• Nested Pebbles and Transitive Closure
• scientific article; zbMATH DE number 408785
• Pebble weighted automata and transitive closure logics
• Transitive closure logic, nested tree walking automata, and XPath
• Expressive Power of Pebble Automata

Cited in

(12)

• Automata on finite trees
• On defining linear orders by automata
• Reversibility of computations in graph-walking automata
• XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
• Transitive closure logic, nested tree walking automata, and XPath
• scientific article; zbMATH DE number 408785 (Why is no real title available?)
• Pebble weighted automata and weighted logics
• Nested Pebbles and Transitive Closure
• Nondeterministic tree-walking automata are not closed under complementation
• Two-way pebble transducers for partial functions and their composition
• Complementing deterministic tree-walking automata
• Automata for XML -- a survey

This page was built for publication: Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure

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