On the power of Las Vegas II: Two-way finite automata

DOI10.1016/S0304-3975(00)00155-9zbMath0983.68098OpenAlexW1971083528MaRDI QIDQ5958109

Georg Schnitger, Juraj Hromkovič

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00155-9

zbMATH Keywords

randomized computationstwo-way finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Probabilistic length-reducing two-pushdown automata, Infinite vs. finite size-bounded randomized computations, Complementing two-way finite automata, Size complexity of rotating and sweeping automata, On probabilistic pushdown automata, Note on the complexity of Las Vegas automata problems, Communication complexity method for measuring nondeterminism in finite automata

Cites Work

• Communication complexity
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Computational Complexity of Probabilistic Turing Machines
• Communication Complexity
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• Nondeterminism and the size of two way finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item