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

DOI10.2168/LMCS-3(2:3)2007zbMath1128.03027MaRDI QIDQ5310688

Hendrik Jan Hoogeboom, Joost Engelfriet

Publication date: 11 October 2007

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

Mathematics Subject Classification ID

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

Related Items (8)

Complementing deterministic tree-walking automata ⋮ Automata for XML -- a survey ⋮ 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 ⋮ Pebble Weighted Automata and Weighted Logics ⋮ Two-way pebble transducers for partial functions and their composition ⋮ Automata on finite trees

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