Translation from classical two-way automata to pebble two-way automata

DOI10.1051/ita/2011001zbMath1211.68232OpenAlexW2035005825MaRDI QIDQ2998731

L'Ubomíra Ištoňová, Viliam Geffert

Publication date: 10 May 2011

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/245613

zbMATH Keywords

finite automataregular languagesdescriptional complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (3)

A time to cast away stones ⋮ Reversibility of computations in graph-walking automata ⋮ Two-way pebble transducers for partial functions and their composition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the state complexity of reversals of regular languages
• On pebble automata
• Finite automata and unary languages
• Halting space-bounded computations
• Lower bounds on the size of sweeping automata
• Space bounded computations: Review and new separation results
• Bridging across the \(\log(n)\) space frontier
• Turing machines with sublogarithmic space
• Complexity results for two-way and multi-pebble automata and their logics
• Converting two-way nondeterministic unary automata into simpler automata.
• Complementing two-way finite automata
• Optimal Simulations between Unary Automata
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Nondeterminism and the size of two way finite automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata

This page was built for publication: Translation from classical two-way automata to pebble two-way automata