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

The investigation of the computational power of randomized computations is one of the central tasks of complexity and algorithm theory. While for one-way finite automata the power of different computational modes was successfully determined, one does not have any nontrivial result relating the power...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2001-07, Vol.262 (1-2), p.1-24
Main Authors: Hromkovič, Juraj, Schnitger, Georg
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Automata. Abstract machines. Turing machines
Computer science
control theory
systems
Exact sciences and technology
Mathematical analysis
Mathematics
Measure and integration
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The investigation of the computational power of randomized computations is one of the central tasks of complexity and algorithm theory. While for one-way finite automata the power of different computational modes was successfully determined, one does not have any nontrivial result relating the power of determinism, Las Vegas and nondeterminism for two-way finite automata. The main results of this paper are as follows.(i)If, for a regular language L, there exist small two-way nondeterministic finite automata for both L and Lʗ, then there exists a small two-way Las Vegas finite automaton for L.(ii)There is a quadratic gap between nondeterminism and Las Vegas for two-way finite automata.(iii)For every k∈N, there is a regular language Sk such that Sk can be accepted by a two-way Las Vegas finite automaton with O(k) states, but every two-way deterministic finite automaton recognizing Sk has at least Ω(k2/log2k) states.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(00)00155-9