TR00-076 Authors: Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

Publication: 18th September 2000 09:14

Downloads: 1126

Keywords:

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].