Complexity results for two-way and multi-pebble automata and their logics

DOI10.1016/S0304-3975(96)00119-3zbMath0874.68213OpenAlexW2069436890MaRDI QIDQ1349896

David Harel, Noa Globerman

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00119-3

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (16)

The equivalence of pebbles and sensing heads for finite automata ⋮ Complementing deterministic tree-walking automata ⋮ Typechecking for XML transformers ⋮ From bidirectionality to alternation. ⋮ A time to cast away stones ⋮ Reversibility of computations in graph-walking automata ⋮ Adding pebbles to weighted automata: easy specification \& efficient evaluation ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ Attribute grammars for unranked trees as a query language for structured documents ⋮ Unnamed Item ⋮ Alternation in two-way finite automata ⋮ A Rice-style theorem for parallel automata ⋮ Two-way pebble transducers for partial functions and their composition ⋮ State complexity of unique rational operations ⋮ Alternation and bounded concurrency are reverse equivalent. ⋮ Query automata over finite trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of sweeping automata
• Alternation with a pebble
• Complexity measures for regular expressions
• Propositional dynamic logic of regular programs
• Propositional dynamic logic of flowcharts
• Alternation
• On the power of bounded concurrency I
• Two-way automata and length-preserving homomorphisms
• State-complexity of finite-state devices, state compressibility and incompressibility

This page was built for publication: Complexity results for two-way and multi-pebble automata and their logics