期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：While deterministic finite automata seem to be well understood, surprisingly
many important problems
concerning nondeterministic finite automata (nfa's) remain open.
One such problem area is the study of different measures of nondeterminism in
finite automata and the
estimation of the sizes of minimal nondeterministic finite automata. In this
paper the concept of
communication complexity is applied in order to achieve progress in this
problem area. The main
results are as follows:
1. Deterministic communication complexity provides lower bounds on the size of
unambiguous nfa's. Applying
this fact, the proofs of several results about nfa's with limited ambiguity
can be simplified.
2. For an nfa A we consider the complexity measures advice_A(n) as the number
of advice bits,
ambig_A(n) as the number of accepting computations, and leaf_A(n) as the
number of computations for
worst case inputs of size n. These measures are correlated as follows
(assuming that the nfa A is
minimal):
advice_A(n), ambig_A(n) lower-equal leaf_A(n) lower-equal O(advice_A(n)
times ambig_A(n)).
3. leaf_A(n) is always either a constant, between linear and polynomial in n,
or exponential in n.
4. There is a family of languages KON_{k^2} with an exponential size gap
between nfa's with
polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially
provides an answer to the
open problem posed by Ravikumar and Ibarra [SIAM J. Comput. 18 (1989),
1263--1282], and Hing Leung
[SIAM J. Comput. 27 (1998), 1073--1082].
