On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata

DOI10.1016/J.JCSS.2003.11.007zbMath1069.68061OpenAlexW2091661846MaRDI QIDQ596324

Katsushi Inoue, Juraj Hromkovič, Pavol Ďuriš

Publication date: 10 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.11.007

zbMATH Keywords

ComplexityNondeterminismLas Vegas randomizationTwo-dimensional finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (1)

On probabilistic pushdown automata

Cites Work

• On measuring nondeterminism in regular languages
• Communication complexity
• Lower bounds for language recognition on two-dimensional alternating multihead machines
• Amounts of nondeterminism in finite automata
• On the relation between ambiguity and nondeterminism in finite automata
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Non-deterministic communication complexity with few witnesses
• Amplification of slight probabilistic advantage at absolutely no cost in space
• Classes of bounded nondeterminism
• Two-dimensional alternating turing machines with only universal states
• Computational Complexity of Probabilistic Turing Machines
• Communication Complexity
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata