文章基本信息

标题：On the Power of Las Vegas II: Two-Way Finite Automata
本地全文：下载
作者：Juraj Hromkovic ; Georg Schnitger
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. This paper continues in the comparison of the computational power of LasVegas computations with the computational power of deterministic and nondeterministic ones. While for one-way finite automata the comparison of different computational modes was successfully determined one does not have any nontrivial result relating the powers of determinism, Las Vegas and nondeterminism for two-way finite automata. The four main results of this paper are the following ones: 1, If, for a regular language L, there exist small two-way nondeterministic finite automata for both L and the complement of L, then there exists a small two-way Las Vegas finite automaton for L. 2, There is a quadratic gap between nondeterminism and LasVegas for the size of two-way finite automata. 3, There is an almost quadratic gap between Las Vegas and determinism for the size of two-way finite automata. 4, Two-way Las Vegas finite automata can be much more powerful than one-way nondeterministic finite automata. A consequence is an exponential gap between one-way Las Vegas finite automata and two-way Las Vegas finite automata.
关键词：determinism, Las Vegas randomization, lower bounds on descriptional complexity, nondeterminism, two-way finite automata