Alternation with a pebble

DOI10.1016/0020-0190(91)90208-YMaRDI QIDQ1178189zbMATH OpenFDO

Authors A. Goralčíková, Pavel Goralčík, Václav Koubek

Publication date 26 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90208-Y

zbMATH Keywords

alternationfinite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Translation from classical two-way automata to pebble two-way automata
• An alternating hierarchy for finite automata
• One alternation can be more powerful than randomization in small and fast two-way finite automata
• scientific article; zbMATH DE number 3911710
• scientific article; zbMATH DE number 1318511

Cited in

(11)

• On the power of white pebbles
• A note on the space complexity of some decision problems for finite automata
• Complexity results for two-way and multi-pebble automata and their logics
• Translation from classical two-way automata to pebble two-way automata
• Two-way finite automata with a write-once track
• Complexity results for multi-pebble automata and their logics
• Two-way automata and length-preserving homomorphisms
• The equivalence of pebbles and sensing heads for finite automata
• Translation from classical two-way automata to pebble two-way automata
• A time to cast away stones
• A time to cast away stones: on a family of pebble automata

This page was built for publication: Alternation with a pebble

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