Communication complexity method for measuring nondeterminism in finite automata.
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 nfa's with bounded unambiguity. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified and presented in a uniform way. (2) There is a family of languages KONk2 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 B. Ravikumar and O. Ibarra (1989, SIAM J. Comput. 18, 1263-1282) and H. Leung (1998, SIAM J. Comput. 27, 1073-1082).
Introduction
In this paper the classical models of one-way nite automata (dfa's) and their
nondeterministic counterparts (nfa's) [RS59] are investigated. While the
structure and fundamental properties of dfa's are well understood, this is not
the case for nfa's. For instance, we have ecient algorithms for constructing
minimal dfa's, but the complexity of approximating the size of a minimal
nfa is still unresolved (whereas nding a minimal nfa solves a PSPACE
complete problem). Hromkovic, Seibert and Wilke [HSW97] proved that
the gap between the length of regular expressions and the number of edges
of corresponding nfa's is between n log 2 n and n log n, but the exact relation
is unknown. Another principal open question is to determine whether there
is an exponential gap between two-way deterministic nite automata and
two-way nondeterministic ones. The last partially successful attack on this
problem was done in the late seventies by Sipser [S80], who established
an exponential gap between determinism and nondeterminism for so-called
sweeping automata (the property of sweeping is essential [M80]). The largest
known gap for the general case is quadratic [HS99].
Our main goal is to contribute to a better understanding of the power of
nondeterminism in nite automata (see [RS59], [MF71], [Mo71], [Sc78] for
very early papers on this topic). We focus on the following problems:
1. The best known method for proving lower bounds on the size of minimal
nfa's is based on nondeterministic communication complexity
[Hr97]. All other known methods are special cases of this method.
Are there methods that provide better lower bounds at least for some
languages? How can one prove lower bounds on the size of unambiguous
nfa's (unfa's), that is nfa's which have at most one accepting
computation for every word?
2. It is a well known fact [MF71], [Mo71] that there is an exponential gap
between the sizes of minimal dfa's and nfa's for some regular languages.
This is even known for dfa's and unfa's [Sc78], [SH85], [RI89], for unfa's
and nfa's with constant ambiguity [Sc78], [RI89], and for ufa's with
polynomial ambiguity and nfa's [HL98]. 1 But, it is open [RI89], [HL98]
whether there exists an exponential gap between the sizes of minimal
nfa's with constant ambiguity and nfa's with polynomial ambiguity.
3. The degree of nondeterminism is measured in the literature in three different
ways. Let A be an nfa. The rst measure advice A (n) equals the
number of advice bits for inputs of length n, i.e., the maximum number
of nondeterministic guesses in computations for inputs of length
n. The second measure leaf A (n) determines the maximum number of
We apologize for claiming the above results as our contribution in the extended abstract
of this paper [HKK00] instead of referring to [Sc78], [SH85], [RI89], [HL98]
computations for inputs of length n. ambig A (n) as the third measure
equals the maximum number of accepting computations for inputs of
length at most n. Obviously the second and third measure may be
exponential in the rst one. The question is whether the measures are
more specically correlated.
To attack these problems we establish some new bridges between automata
theory and communication complexity. The communication complexity
of two-party protocols was introduced by Yao [Y79] (and implicitly
considered by Abelson [Ab78], too). The initial goal was to develop
a method for proving lower bounds on the complexity of distributive and
parallel computations (see, for instance, [Th79, Th80, Hr97, KN97]). Due
to the well developed, nontrivial mathematical machinery for determining
the communication complexity of concrete problems (see, for instance
[AUY83, DHS96, Hr97, Hr00, KN97, L90, NW95, PS82]), communication
complexity has established itself as a sub-area of complexity theory. The
main contributions of the study of communication complexity lie especially
in proving lower bounds on the complexity of specic problems, and in comparing
the power of dierent modes of computation.
Here, for the rst time, communication complexity is applied for the
study of nondeterministic nite automata, with the emphasis on the tradeo
between the size and the degree of nondeterminism of nfa's. Our procedure
is mainly based on the following facts:
(i) The theory of communication complexity contains deep results about
the nature of nondeterminism (see, e.g. [KNSW94, HS96]) that use the
combinatorial structure of the communication matrix as the computing
problem representation.
(ii) In [DHRS97, Hr97, HS00], the non-uniform model of communication
protocols for computing nite functions was extended to a uniform
model for recognizing languages in such a way that several results
about communication complexity can be successfully applied for uniform
computing models like automata.
Combining (i) and (ii) with building of new bridges between communication
complexity and nfa's we establish the following main results.
1. Let cc(L) resp. ncc(L) denote the deterministic resp. nondeterministic
communication complexity of L. It is well known that 2 cc(L) and
2 ncc(L) are lower bounds on the sizes of the minimal dfa for L and a
minimal nfa for L respectively. First we show that there are regular
languages L for which there is an exponential gap between 2 ncc(L) and
the minimal size of nfa's for L. This means, that the lower bound
method based on communication complexity may be very weak. Then
we show as a somewhat surprising result that 2
cc(L)=k 2 is a lower
bound on the size of nfa's with ambiguity k for L. We furthermore show
that Rank(M) 1=k 1 is a lower bound for the number of states for
nfa's with ambiguity k, where M is a communication matrix associated
with L. It is possible that this lower bound is always better than the
rst one (see [KN97] for a discussion of the quality of the so-called
rank lower bound on communication complexity).
As a corollary we present a sequence of regular languages NIDm such
that the size of a minimal nfa is linear in m, while the size of every
unfa for NIDm is exponential in m. This substantially simplies the
proofs of similar results in [Sc78], [SH85].
2. We establish the relation
advice A (n); ambig(n) A  leaf A (n)  O(advice A (n)  ambig A (n))
for any minimal nfa A. Observe that the upper bound on leaf A (n) implies
that minimal unambiguous nfa's may have at most O(advice A (n))
O(n) dierent computations on any input of size n, and an exponential
gap between advice A (n) and leaf A (n) is possible only if the
degree of ambiguity is exponential in n.
Furthermore we show that leaf A (n) is always either bounded by a
constant, or at least linear but polynomially bounded, or otherwise at
least exponential in the input length.
3. We present another sequence of regular languages than in [HL98] with
an exponential gap between the size of nfa's with exponential ambi-
guity, and nfa's with polynomial ambiguity. This result is obtained
by showing that small nfa's with polynomial ambiguity for the Kleene
closure (L#)  imply small unfa's that work correctly on a polynomial
fraction of inputs. Our technique is more general than the proof
method of Hing Leung [HL98] and provides an essentially shorter
proof.
Furthermore we describe a sequence of languages KON k 2 such that
there is an exponential gap between the size of nfa's with polynomial
ambiguity and nfa's with ambiguity k. This provides a partial answer
to the open question [RI89], [HL98] whether there is an exponential
gap between minimal nfa's with constant ambiguity and minimal nfa's
with polynomial ambiguity.
This paper is organized as follows. In section 2 we give the basic deni-
tions and x the notation. In order to increase the readability of this paper
for readers who are not familiar with communication complexity theory,
we give more details about communication protocols and build the basic
intuition of their relation to nite automata. Section 3 is devoted to the
investigation of the relation between the size of nfa's and communication
complexity. Section 4 studies the relation between dierent measures of
nondeterminism in nite automata, and presents the remaining results.
Denitions and Preliminaries
We consider the standard one-way models of nite automata (dfa's) and
nondeterministic nite automata (nfa's). For every automaton A, L(A)
denotes the language accepted by A. The number of states of A is called
the size of A and denoted size A . For every regular language L we denote
the size of the minimal dfa for L by s(L) and the size of minimal nfa's
accepting L by ns(L). For every alphabet ,  ng and
ng.
For any nfa A and any input x we use the computation tree T A;x to
computations of A on x. Obviously the number of leaves of
T A;x is the number of dierent computations of A on x.
The ambiguity of an nfa A on input x is the number of accepting computations
of A on x, i.e., the number of accepting leaves of T A;x . If the nfa
A has ambiguity one for all inputs, then A is called an unambiguous nfa
(unfa) and uns(L) denotes the size of a minimal unfa accepting L. More
generally, if an nfa A has ambiguity at most k for all inputs, then A is called
a k-ambiguous nfa and ns k (L) denotes the size of a minimal k-ambiguous
nfa accepting L.
For every nfa A we measure the degree of nondeterminism as follows.
Let  denote the alphabet of A. For every input x 2   and for every computation
C of A on x we dene advice(C) as the number of nondeterministic
choices during the computation C, i.e., the number of nodes on the path of
C in T A;x which have more than one successor. Then
advice A is a computation of A on xg
and advice A
For every x 2   we dene leaf A (x) as the number of leaves of T A;x and
set
leaf A
For every x 2   we dene ambig A (x) as the number of accepting leaves
of T A;x and set
ambig A
Since a language need not contain words of all lengths we dene ambiguity
over all words of length at most n which makes the measure monotone.
Observe that the leaf and advice measures are monotone as well.
Note that dierent denitions have been used by other authors; see e.g.
[GLW92], where the number of advice bits is maximized over all
inputs and minimized over all accepting computations on those inputs. In
this case there are nfa's which use more than constant but less than linear (in
the input length) advice bits, but this behavior is not known to be possible
for minimal nfa's.
To prove lower bounds on the size of nite automata we shall use two-party
communication complexity. This widely studied measure was introduced
by Yao [Y79] and is the subject of two monographs [Hr97], [KN97].
First, we introduce the standard, non-uniform model of (communica-
tion) protocols for computing nite functions. A (two-party communi-
consists of two computers C I and C II of unbounded
computational power (sometimes called Alice and Bob in the literature)
and a communication link between them. P computes a nite function
in the following way. At the beginning C I gets an input
obtains an input  2 V . Then C I and C II communicate
according to the rules of the protocol by exchanging binary messages until
one of them knows f(; ). C I and C II may be viewed as functions in this
communication, where the arguments of C I (C II ) are its input  () and
the whole previous communication history (the sequence c 1 of
all messages exchanged between C I and C II up until now), and the output
is the new message submitted. We also assume that C I (C II ) completely
knows the behavior of C II (C I ) in all situations (for all arguments). Another
important assumption is that every protocol has the prex-freeness
property. This means, that for any ;
any communication
history , the message C I (;
of C I (
prex of C II (
))]. Informally, this means that the messages
are self-delimiting and we do not need any special symbol marking the end
of the message.
Formally, the computation of a protocol (C I ; C II ) on an input is a sequence
are the
messages and
2 Z is the result of the computation. The communication
complexity of the computation of P on an input (; ) is the sum
of the lengths of all messages exchanged in the communication. The communication
complexity of the protocol P , cc(P ), is the maximum of
the communication complexities over all inputs from U  V .
Due to the prex-freeness property of messages we have that if, for two
computations
and
then and a protocol
allows m dierent computations, then its communication complexity must
be at least dlog 2 me 1.
The communication complexity of f , cc(f), is the communication
complexity of the best protocol for f , i.e.,
The protocols whose computations consist of one message only (i.e., C I
sends a message to C II and then C II must compute the result) are called
one-way protocols. For every nite function f ,
is a one-way protocol computing fg
is the one-way communication complexity of f .
The representation of a nite function f : UV ! f0; 1g by the so-called
communication matrix is very helpful for investigating the communication
complexity of f . The communication matrix of f is the jU jjV j Boolean
matrix M f [u; v] dened by
for all u 2 U and v 2 V . So, M f [u; v] consists of jU j rows and jV j columns.
If one wants to x this representation (which is not necessary for the relation
to the communication complexity of f ), one can consider some kind
of lexicographical order for elements in U and V . But, the special order of
rows and columns does not matter for our applications.

Figure

1 presents the communication matrix M f for the Boolean function
dened by
where  is addition modulo 2.
Denition 1. Let be two sets and
. For every  2 U , the row
of  in M f is
row
For every  2 V , the column of  in M f is
is the number of dierent rows of M f .
A submatrix of M f is any intersection of a non-empty set of rows with
a non-empty set of columns. A -monochromatic submatrix,  2 f0; 1g
of M f is any submatrix of M f whose elements are all equal to  (Figure 1
depicts the 1-monochromatic submatrix that is the intersections of rows 001,
010, 100 and 111 with the columns 000, 011, 101 and 110).
Figure
be a set of monochromatic submatrices of a
Boolean matrix M f . We say that S is a cover of M f if, for every element
a  of M f , there exists an m 2 kg such that a  is an element of
Mm . We say that S is an exact cover of M f if S is a cover of M f and
kg. The tiling complexity
of M f is
is an exact cover of M f g
ut
The work of a protocol (C I ; C II ) for f can be viewed as a game on the
communication matrix M f . C I with input  knows the row row  , C II with
input  knows the column column  , and they have to determine f(; ). 2
A communication message c 1 submitted from C I to C II can be viewed as
the reduction of M f to a submatrix M f consisting of rows for which C I
sends c 1 because C II knows the behavior of C I . Similarly the second message
2 sent from C II to C I restricts M f
of the columns of M f (c 1 ) for which C II with the second argument c 1 sends
2 Note that they do not need to estimate the coordinates of the intersection of row
and column  .
knows the result. So, every computation of (C I ; C II ) that nishes
with 1 (0) denes a 1-monochromatic (0-monochromatic) submatrix of M f .
This means that all inputs (; ) contained in this monochromatic submatrix
have the same computation of the protocol C I and C II . So, (C I ; C II )
unambiguously determine an exact cover of M f by monochromatic subma-
trices. More precisely, a protocol with k dierent computations determines
an exact cover of cardinality k. The immediate consequence is:
Fact 1. For every nite function
Another important consequence is the following fact.
Fact 2. For every nite function
(Row (M f ))e:
Proof: For no two dierent rows row  and row  , a one-way protocol
computing f can send the same message c because C II cannot determine the
result for any  such that column  has dierent values on the intersections
with row  and row  . On the other hand, Row dierent messages are
enough (one message for a group of identical rows) to construct a one-way
protocol for f . ut
Since the number of 1-monochromatic matrices in any exact cover of all
ones in M f is a trivial upper bound on the rank of M f , Fact 1 implies:
Fact 3. For every nite function every eld F with
neutral elements
cc(f)  dlog 2 (Rank F (M f ))e:
Let Q be the set of rational numbers. Since it is well-known that
is a eld with neutral elements 0 and 1g
we formulate Fact 3 as
for every nite function f .
Now, we consider nondeterministic communication complexity and its
relation to some combinatorial properties of M f . A nondeterministic
protocol P computing a nite function consists of two
nondeterministic computers C I and C II that have a nondeterministic choice
from a nite number of messages for every input argument. For any input
we say that that P accepts (;
there exists a computation of P on (; ) that ends with the result 1. So,
computes 0 for an input (; ) (rejects (; )) if all computations of P
on (; ) end with the result 0. The nondeterministic communication
complexity of P , denoted ncc(P ), is the maximum of the communication
complexities of all accepting computations of P . The nondeterministic
communication complexity of f is
is a nondeterministic protocol computing fg
Let ncc 1 (f) denote the one-way nondeterministic communication
complexity of f .
Similarly as in the deterministic case, every accepting computation of P
for f unambiguously determines a 1-monochromatic submatrix of M f and
the union of all such 1-monochromatic submatrices must cover all the 1's of
M f but no 0 of M f . The dierence to the deterministic case is that these
1-monochromatic submatrices may overlap, which corresponds to the fact
that P may have several dierent accepting computations on a given input.
Denition 2. Let M f be a Boolean matrix, and let
be a set of 1-monochromatic submatrices of M f . We say that S is a 1-cover
of M f if every 1 of M f is contained in at least one of the 1-submatrices of
S. We dene
is a 1-cover of M f g:
ut
Fact 4. For every nite function
Proof: The above consideration showing that a nondeterministic protocol
with m accepting computations determines a 1-cover of M f of cardinality
implies
Since ncc(f)  ncc 1 (f) for every f , it is sucient to prove ncc 1 (f)
be a 1-cover of M f . A one-way
nondeterministic protocol (C I ; C II ) can work on an input (; ) as
follows. C I with input  nondeterministically chooses one of the matrices
of S with a non-empty intersection with row  and sends the binary code
of its index i to C II . If column  has a non-empty intersection with M i ,
then C II accepts. Since dlog 2 me message length suces to code m dierent
messages,
The rst trivial bridge [Hr86] between automata and communication
complexity says that
for every regular language L    and every positive integer n, where
L. The argument for this lower
bound is very simple. Let A be a dfa (nfa) accepting L with s(L) (ns(L))
states. Then a one-way protocol can compute f 2n;L as follows. For an input
, C I simulates the work of A on  and sends the name of the state q reached
by A after reading  to C II . C II continues in the simulation of the sux
from the state q. If A accepts , then (C I ; C II ) accepts (; ).
Unfortunately, the lower bound (1) may be arbitrarily bad for both s(L)
and ns(L) because this non-uniform approach cannot completely capture
the complexity of the uniform acceptance of L. We shall overcome this
diculty in the next section.
3 Communication Complexity and Finite
Automata
To improve lower bounds on s(L) and ns(L) by communication complexity,
Duris, Hromkovic, Rolim, and Schnitger [DHRS97] (see also [Hr86, HS00])
introduced uniform protocols and communication matrices of regular languages
as follows. For every regular language L    , we dene the innite
Boolean matrix
a
Since every regular language has a nite index (Myhill-Nerode theorem), the
number of dierent rows of ML is nite. So, we can again use the protocols
as nite devices for accepting L.
Denition 3. Let  be an alphabet and let L    . A one-way uniform
protocol over  is a pair (C I ; C II ), where
is a function with the prex freeness property, and
fC I () j  2   g is a nite set, and
rejectg is a function.
We say that
The message complexity of the protocol D is
(i.e., the number of the messages used by D), and the message complexity
of L is
is a one-way uniform protocol accepting Lg:
The communication complexity of D is
and the one-way communication complexity of L is
is a one-way uniform protocol accepting Lg:
ut
If one wants to give a formal denition of a one-way nondeterministic
protocol over , it is sucient to consider C I as a function from   to a
nite subset of f0; 1g  . The acceptance criterion of L changes to
I () such that accept 2 C II (; c)) ,  2 L:
denote the one-way nondeterministic message
[communication] complexity of L. We observe that the main dierence
between uniform protocols and (standard) protocols is the way the input
is partitioned between C I and C II . If a protocol D computes a Boolean
one can view this as the partition of
inputs of f (from f0; 1g r+s ) into the prex of r bits and a sux of s bits (i.e.
assigning the rst r bits to C I and the rest to C II ), and a communication
between C I and C II in order to compute the value of f . A uniform protocol
over  considers, for every input partitions of
for each of these partitions it must accept (reject) if  2 L ( 62 L). This
means, that the matrices are special Boolean matrices with
a ;1 ::: and a uniform protocol D for L
must recognize the membership of  to L for every partition of  between
C I and C II .
The following result from [DHRS97, HS00] shows in fact that one-way
uniform protocols are nothing else but deterministic nite automata.
Fact 5. Let  be an alphabet. For every regular language L    ,
The idea of Proof: just a reformulation of
the Myhill-Nerode theorem. In Section 2 we have already observed that
Row (ML ) is exactly the number of dierent messages used by an optimal
one-way protocol. 3 ut
Following the idea of the simulation of a nite automaton by a protocol
in the nondeterministic case, we have the following obvious fact [Hr97].
Fact 6. For every alphabet  and every regular language L    ,
Fact 6 provides the best known lower bound proof technique on the size of
minimal nfa's. All previously known techniques like the fooling set approach
are special cases of this approach. Moreover the fooling set method, which
covers all previous eorts in proving lower bounds on ns(L), can (for some
languages) provide exponentially smaller lower bounds than the method
based on nondeterministic communication complexity [DHS96].
The rst question is therefore whether nmc(L) can be used to approximate
ns(L). Unfortunately this is not possible. Note that a result similar
to Lemma 1 was also independently established by Jiraskova [Ji99].
Lemma 1. There exists a sequence of regular languages fPART n g 1
n=1 such
that
Proof: Let PART
For the next considerations it is important to observe that the condition
equivalent to the condition x 6= z _ First we
describe a nondeterministic uniform protocol (C I ; C II ) for PART n which
uses O(n 2 ) messages.
Players C I and C II compute the lengths l I ; l II of their inputs. C I communicates
l I and C II rejects when l I l II 6= 3n. So we assume that
l I in the following.
Case 1: l I  n.
C I chooses a position 1  i  l I and communicates I . C II accepts,
accepts if and only if
Observe that if x 6= z, then there is an accepting computation because
there exists i such that x i 6= z i . If however
that is i y.
Case 2: n < l I  2n.
C I chooses a position 1  i  n and communicates I . Furthermore,
C I compares x I n and sends the bit 1, if the
strings are equal and the bit 0 if the strings are dierent. C II accepts if x i 6=
z i . Otherwise (if x
3 The fact that ML is innite does not matter because ML has a nite number of
dierent rows. Moreover, it would work for an innite number of dierent rows (i.e., for
automata with an innite number of states), too [Eil74].
If the two strings are equal and the bit 1 was received, then C II accepts and
rejects otherwise.
Note that if x 6= z then there is an accepting computation. If not, then
C II accepts if and only if
Case 3: 2n < l I  3n.
C I chooses a position l I 2n < i  n and communicates I . Furthermore
C I compares x with y. If
then C I accepts. Otherwise C II accepts if and only if x i 6= z i .
The protocol uses O(n 2 ) messages, so nmc(PART n
Now, we prove that ns(PART N
. Obviously, every nfa B accepting
must have the following properties:
there is an accepting computation
of B on every word xxx or x 2 f0; 1g n , and
i.e. there is
no accepting computation of B on any word xyx with x 6=
We prove that every nfa satisfying (i) and (ii) must have at least 2 nstates. Let us assume the opposite. Let A be a nfa with fewer than 2 nstates that satises (i) and (ii). Since L 1  L(B), there exists an accepting
computation C x on xxx for every x 2 f0; 1g n . Let P attern(C x
where p is the state of C x after reading x and q is the state of C x after
reading xx. Since the number of states is smaller than 2 n
2 , the number of
dierent patterns is smaller than 2 . So, there exist two words
v, such that P attern(C u
some states This means that starting to work from r on u as well as on
v one can reach s after reading u or v. The immediate consequence is that
there are accepting computations of B on uvu and vuv as well. Since u 6= v,
uvu and vuv belong to L 2 , a contradiction with condition (ii). ut
To nd lower bound methods for ns(L) that provide results at most
polynomially smaller than ns(L) is one of the central open problems on
nite automata. In the following, we concentrate on lower bounds for nfa's
with constant ambiguity. Even for unambiguous automata no nontrivial
general method for proving lower bounds has been known up to now.
To introduce our method for proving lower bounds on nfa's with bounded
ambiguity we have to work with the communication matrices for regular
languages. In Fact 5 we have observed that every matrix ML has a -
nite number of dierent rows, which is the index s(L) of the regular language
L (this means that there exists a s(L)  s(L) (nite) submatrix M
of ML such that Row
every eld F with neutral elements
and Thus, instead of introducing the general
two-way uniform communication protocols), we dene the communication
complexity of L, denoted cc(L), as the communication complexity of the
best protocol for the communication matrix ML . Because of the denition
of ML , this approach covers the requirement that the protocol correctly decides
membership of any input to L for any prex-sux partition of the
input.
Before formulating the main result of this section we build our intuition
about the connection between cc(L) and uns(L). If one simulates an unambiguous
automaton by a nondeterministic one-way protocol in the standard
way described above, then the resulting protocol is unambiguous, too. This
means that every 1 in ML is covered by exactly one accepting computation,
i.e., the unfa A determines an exact cover of all 1's in ML of cardinality
size A . The similarity to the deterministic communication complexity is that
any such protocol determines an exact cover of all elements of the communication
matrix by monochromatic submatrices. Some nontrivial results from
communication complexity theory [KNSW94] are needed to relate cc(L) and
uns(L) via the outlined connection.
Theorem 1. For every regular language L    ,
a) uns(L)  RankQ (ML ),
ns k (L)  RankQ (ML ) 1=k 1,
c) ns k (L)  2
cc(L))=k 2.
Proof: Let A be an optimal unfa for L. A can be simulated by a
one-way nondeterministic protocol as follows: C I simulates A on its input
and communicates the obtained state. C II continues the simulation and
accepts/rejects accordingly. Obviously the number of messages is equal to
size A and the protocol works with unambiguous nondeterminism.
It is easy to see that the messages of the protocol correspond to size A
many submatrices of the matrix ML covering all ones exactly once. Hence
the rank is at most size A and we have shown a), which is the rank lower
bound on communication complexity [MS82] (see Fact 3 in Section 2).
For b) observe that the above simulation induces a cover of the ones in
ML so that each one is covered at most k times. By the following fact from
[KNSW94] we are done:
Fact 7. Let  r (M) denote the minimal size of a set of submatrices covering
the ones of a Boolean matrix M so that each is covered at most r times.
Then
For the other claim again simulate A by a one-way k-ambiguous nondeterministic
protocol with size A messages.
The results of [KNSW94] (see also [L90], [Y91]) imply that a k-ambigu-
ous nondeterministic one-way protocol with m messages can be simulated
by a deterministic two-way protocol with communication log(m
log(m
cc(L)  log(size k
and c) follow. ut
Before giving an application of the lower bound method we point out
that neither 2
nor RankQ (ML ) is a lower bound method capable of
proving polynomially tight lower bounds on the minimal size of unfa's for all
languages. In the rst case this is trivial, in the second case it follows from a
modication of a result separating rank from communication complexity (see
[KN97]). But the gap between RankQ (ML ) and uns(L) may be bounded
by a pseudo-polynomial function.
Now we apply Theorem 1 in order to present an exponential gap between
ns(L) and uns(L) for a specic regular language. Let, for every positive
integer m; g.
Theorem 2. For every positive integer m
(i) NIDm can be recognized by an nfa A with ambiguity O(m) and size
O(m)
(ii) Any nfa with ambiguity k for NIDm has size at least 2 m=k 1, and
in particular any unfa for NIDm must have states.
log m) for NIDm has polynomial size
in m.
Proof:
(i) First the nfa guesses a residue i modulo m, and then checks whether
there is a position p
(ii) Observe that the submatrix spanned by all words u and v with
is the \complement" of the 2 m  2 m identity matrix. The
result now follows from the assertions a) and b) of Theorem 1.
(iii) is an immediate consequence of (ii). ut
We see that the proof of Theorem 2 is a substantial simplication of the
proofs of similar results presented in [Sc78], [SH85].
4 Degrees of Nondeterminism in Finite Automata
It is easy to see that advice A (n)  leaf A (n)  2 O(advice A (n)) and also that
ambig A (n)  leaf A (n) for every nfa A. The aim of this section is to investigate
whether stronger relations between these measures hold.
Lemma 2. For all nfa A either
a) advice A (n)  size A and leaf A (n)  size size A
A or
advice A (n)  n=size A 1 and leaf A (n)  n=size A 1.
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@

Figure
Proof: If some reachable state q of A belongs to a cycle in A and if
q has two edges with the same label originating from it such that one of
these edges belongs to the cycle, then advice A (n)  (n size A )=size A
n=size A 1. Otherwise for all words all states with a nondeterministic
decision are traversed at most once. ut
Our next lemma relates the leaf function to ambiguity. The initial idea
is that a computation tree of any minimal unfa A on any input w could
look like the tree from Figure 2. There is exactly one path P from the
root to a leaf (a computation) with several nondeterministic guesses and
all paths having only one vertex in common with P do not contain any
nondeterministic branching. In other words, if a computation branches into
two computations P 1 and P 2 , then at least one of P 1 and P 2 should be
completely deterministic. We are not able to verify this nice structure, but
the next result shows that any computation tree of a minimal unfa A is very
thin because every level of this tree can contain at most size A + 1 dierent
computations.
In what follows a state q of an nfa A is called terminally rejecting, if there
is no word and no computation of A, such that A accepts when starting in
q, i.e.,   (q; v) contains no accepting state for any word v. Clearly there
is at most one terminally rejecting state in a minimal automaton, because
otherwise these states can be joined reducing the size. Call all other states
of A undecided.
Lemma 3. Every nfa A with at most one terminally rejecting state satises
leaf A (x)  ambig A (jxj
for all x.
size A ). If the computation tree consists
only of nodes marked with the terminally rejecting state, then the tree has
just one leaf and the claim is trivial. For the general case, consider a level
of the computation tree of A on x that is not the root level. Assume that
the level contains more that k  size A nodes labeled with undecided states
(called undecided nodes). Then one undecided state q must appear at least
times on this level. There are k computations of A on a prex of
x such that q is reached. If q is accepting, then the prex of x is accepted
a contradiction, since ambig A is monotone. If q is
rejecting, but undecided, then there is a word v of length at most size A such
that v is accepted by some computation of A starting in q. But then the
prex of x concatenated with v is accepted by at least k
a contradiction.
Thus each level of the tree that is not the root level contains at most
k  size A undecided nodes. Overall there are at most jxj  k  size A
undecided nodes.
Observe that each node has at most one terminally rejecting child. Thus
the number of terminally rejecting leaves is equal to the number of undecided
nodes that have a terminally rejecting child. Hence the number of terminally
rejecting leaves is at most the number of undecided nodes minus the number
of undecided leaves. Thus the overall number of leaves is at most the number
of terminally rejecting leaves plus the number of undecided leaves which
is at most the number of undecided nodes. So overall there are at most
leaves. ut
Theorem 3. Every nfa A with at most one terminally rejecting state sat-
ises
advice A (n); ambig A (n)  leaf A (n)  O(ambig A (n)  advice A (n)):
Especially for any such unfa: advice A
Proof: Observe that for all n: ambig A
ambig A (n
since ambig A is monotone and at most exponential. ut
Next we further investigate the growth of the leaf function. Lemma 4 is
a variation of a result in [IR86].
Lemma 4. For every nfa A, either leaf A (n)  (nsize A ) size A or leaf A (n) n) .
Proof: Assume that an nfa A contains some state q, such that q can
be reentered on two dierent paths starting in q, where each path is labeled
with the same word w. It is not hard to show that in this case there are
two dierent paths from q to q labeled with a word w of length size 2
A 1.
Then the computation tree of uw m (where u leads from the starting state
to q) has at least 2 m  2 (n size A )=size 2
A leaves, where
Now assume that A does not contain such a state. Then, for each non-deterministic
state q (i.e., a state with more than one successor for the same
letter) and any computation tree, the following holds: If q is the label of a
vertex v, then q appears in each level of the subtree of v at most once.
We prove by induction on the number k (k  size A ) of dierent nondeterministic
states in a computation tree that the number of leaves is at most
(n  size A ) k . The claim is certainly true if there are no nondeterministic
states.
Assume that there are k nondeterministic states, with some state q 1
appearing rst in the tree. Observe that no level in the entire computation
tree contains q 1 more than once.
For each occurrence of q 1 in the computation tree x some child, so
that the overall number of leaves is maximized. We get a tree with one
nondeterministic state less, and by the inductive hypothesis this tree has at
most (n  size A ) k 1 leaves.
appears at most once on each level and since there are at most
size A children of q 1 on each level, there are at most (n  size A ) k leaves. ut
Lemmas 2 and 4 give us
Theorem 4. For every nfa A: leaf A (n) is either bounded by a constant, or
in between linear and polynomial in n, or otherwise 2 (n) .
Now, we consider the dierence between polynomial and exponential
ambiguity resp. polynomial and exponential leaf number. We show that
languages which have small automata of polynomial ambiguity are related
to the concatenation of languages having small unfa's. If the language is
a Kleene closure, then one unfa accepts a large subset. Compare this to
closures are shown to be recognizable as ecient
by nfa's with constant advice as by dfa's.
Theorem 5. a) Let L be an innite regular language and A some nfa for
L with polynomial ambiguity. Then there are d  size A languages L i such
that L 1    L d  L, L i is recognizable by an unfa with O(size A ) states, and
=for innitely many n.
for a regular language K not using the letter # and
let A be some nfa for L with polynomial ambiguity. Then, for all m, there is
an unfa A 0 with O(size A ) states that decides L 0  L such that for innitely
many n
Proof: a) Dene the ambiguity graph of A in the following way: the
nodes are the (reachable) states of A and there is an edge from q i to q j if
there are two paths from q i to q j in A, with the same label sequence. Note
that the ambiguity graph is acyclic i the ambiguity of A is polynomially
bounded as we have seen in the proof of Lemma 4.
Now we construct a unfa A i;j;k which accepts those words that lead in
A from q i to q j and then via one edge to q k . Here, we assume that the
longest path from q i to q k in the ambiguity graph consists of one edge and
q j is reachable from q i in A, but not in the ambiguity graph. Moreover, we
demand that there is an edge in A from q j to q k .
The states of A i;j;k are the states reachable in A from q i , but not reachable
in the ambiguity graph from q i , plus the state q k . The edges are as in
A except that the only edges to q k come from q j . q i is the start. Accepting
state is q k . L i;j;k is the language accepted by A i;j;k .
Now consider the words w 2 L \  n . Each such word is accepted on
some path in A leading from q 0 to some accepting state q a . Fix one such
accepting state so that a constant fraction of all words w is accepted and
make the other accepting states rejecting. On an accepting path for w
the states appear without violating the topological ordering of the ambiguity
graph. So, we may x a sequence of states q
a such that
. Since there are only nitely many such
sequences we are done.
b) Similar to a), we get k languages L decidable by small unfa's
A i , such that
=for innitely many n.
A partition of the letters of words in ( m #) n is given by mapping the
nm letters to the k unfa's. There are at most n
possible
partitions. So some partition must be consistent with accepting paths for
a fraction of 1=poly (n) of (( m \ K)#) n . Fix one such partition. Then for
each words w an unfa is responsible for some prex u, followed
by a concatenation of words of the form # m , and nally a word of the
form #v. For all i we x a prex u i , a sux v i , and states q
entered
when reading the rst and nal occurrence of #, such that as many words
from (( m \ K)#) n as possible are accepted under this xing. At least a
fraction of size k =2 1=poly (n) of (( m \K)#) n has accepting paths
consistent with this xing.
If any A i accepts less than a polynomial fraction (compared to the projection
of (( m \K)#) n to the responsibility region of A i ) then overall less
than a polynomial fraction is accepted. Hence one A i can be found, where
from q i a polynomial fraction of words in ( m \ K)#) n=k leads to non-
terminally rejecting states in A i . Making one non-terminally rejecting state
reached by a # edge accepting and removing the original accepting states
yields an unfa that accepts the desired subset for innitely many n. ut
Applying Theorem 5 we can prove an exponential gap between nfa's and
nfa's with polynomial ambiguity. This proof is also substantially simpler 4
than the proof of an exponential gap between polynomial ambiguity and
exponential ambiguity for the language (0
Theorem 6. There is a family of languages KLm such that KLm can be
recognized by an nfa with advice (n), leaf 2 (n) and size poly(m), while
every nfa with polynomial leaf number/ambiguity needs size at least 2
m)
to recognize KLm .
Proof: Let LNDISJ
from a size m 32 universe and the sets [ non-triviallyg.
Moreover, let
Given a polynomial ambiguity nfa for KLm , we get an unfa accepting
a fraction of 1=poly(n) of (LNDISJ m#) n for innitely many n by Theorem
4b). Then we simulate the unfa by a nondeterministic communication
protocol, where player C I receives all x and player C II all y inputs. The protocol
needs O(n  log size A ) bits to work correctly on a 1=poly(n) fraction of
(LNDISJ m#) n and has unambiguous nondeterminism. A result from [HS96]
implies that this task needs
communication
nm) and thus size A  2
m) .
ut
Thus, we have another strong separation between the size of automata
with polynomial ambiguity and the size of automata with exponential ambi-
guity. The situation seems to be more complicated, if one compares constant
and polynomial ambiguity. Ravikumar and Ibarra [RI89] and Hing Leung
[HL98] considered it as the central open problem related to the degree of
ambiguity of nfa's. Here, we can only show that there is a family KON m of
languages with small size nfa's of polynomial ambiguity, while nfa's of am-
biguity
are exponentially larger. In the following theorem we describe a
candidate for a language that has ecient nfa's only when ambiguity is poly-
nomial. Furthermore the language exhibits an almost optimal gap between
the size of unfa's and polynomial ambiguity nfa's. In the proof the rank of
the communication matrix of KON m is shown to be large by a reduction
from the disjointness problem.
Theorem 7. Let KON contains all
words in f0; 1g  with a number of 1's that is divisible by m. KON m can be
recognized by an nfa A with ambig A (n); leaf A
while any nfa with ambiguity k for KON m needs at least 2 (m 1)=k 2 states.
Proof: Since the upper bound of theorem 7 is obvious, we focus on
proving the lower bound.
Consider the communication problem for the complement of the disjointness
predicate NDISJ l . The inputs are of the form x; y 2 f0; 1g l , where x
4 If the known results about communication complexity are for free (i.e., not included
in the measurement of the proof diculty).
and y are interpreted as incidence vectors of subsets of a size l universe.
The goal is to nd out, whether the two sets have a nontrivial intersection.
Note that the rank of the communication matrix M NDISJ l
is 2 l 1. We
reduce NDISJ m 1 to KON m , i.e., identify a submatrix of MKONm that is
the communication matrix M NDISJ m 1
Consider inputs to KON m of the form 01
and addition over
ZZ m . For any subset s  1g one can nd such an input x s .
These inputs correspond to the rows of our submatrix.
For each subset x an input y s of the
g. These 2 m 1 inputs correspond to the columns of our
submatrix.
Now consider the obtained submatrix: if s and r intersect non-trivially,
then x s y r 2 KON m . On the other hand, if s and r are disjoint, then there
is no sub-word which has a number of 1's divisible by m.
r is not in KON m . We have identied a submatrix of rank 2 m 1 1.
Applying Theorem 1(b) we obtain our lower bound. ut
For every constant m, the language KON m 2 of Theorem 7 can be recognized
with size O(m 2 ), leaf number and ambiguity (n), and advice (n),
while every m ambiguous nfa has size 2
m) . Jurdzinski [Ju00] observed
that KON m 2 can be computed by nfa's with constant ambiguity and size
poly(m). Therefore the analysis of Theorem 7 cannot be improved substan-
tially. Jurdzinski's observation also applies to the language f0; 1g  0 k f0; 1g
which was proposed in [RI89] for separating constant from polynomial ambiguity

5 Conclusions and Open Problems
We have shown that communication complexity can be used to prove lower
bounds on the size of nfa's with small ambiguity. This approach is limited,
because for nontrivial bounds ambiguity has to be smaller than the size
of a minimal nfa. Is it possible to prove lower bounds for automata with
arbitrarily large, but constant ambiguity, when equivalent automata of small
size and polynomial ambiguity exist?
In this context it would be also of interest to investigate the ne structure
of languages with regard to constant ambiguity. At best one could show
exponential dierences between the number of states for ambiguity k and
the number of states for ambiguity k + 1. Observe however, that such an
increase in power is impossible provided that the size of unfa's does not
increase substantially under complementation [K00]. Analogous questions
apply to polynomial and exponential ambiguity.
Are there automata with non-constant but sub-linear ambiguity? A
negative answer establishes Theorem 3 also for ambiguity as complexity
measure.
Other questions concern the quality of communication as a lower bound
method. How far can Rank resp. 2
cc(L) be from the actual size of minimal
unfa's? Note that the bounds are not polynomially tight. Are there
alternative lower bound methods?
Finally, what is the complexity of approximating the minimal number of
states of an nfa?



--R

Lower bounds on information transfer in distributed computations.
On notions of informations transfer in VLSI circuits.



On measuring nondeterminism in regular languages.
On the relation between ambiguity and nondeterminism in




Separating exponentially amgigous




On sparseness

personal communication.

Lower bounds for computation with limited nonde- terminism
On automata with constant ambiguity.
Communication Complexity.

Las Vegas is better than determinism in VLSI and distributed computing.
Economy of description by au- tomata
On the bounds for state-set size in the proofs of equivalence between deterministic

On ranks vs. communication com- plexity
Communication complexity.
Communication Complexity.
Relating the type of ambiguity of
Finite automata and their decision prob- lems
Lower Bounds on the Size of Sweeping Automata.
Succinctness of descriptions of context-free
On the equivalence and containment problems for unambiguous regular expressions

A complexity theory for VLSI.
Expressing combinatorial optimization problems by linear programs.
Some complexity questions related to distributed com- puting
--TR
On sparseness, ambiguity and other decision problems for acceptors and transducers
Communication complexity hierarchy
Relating the type of ambiguity of finite automata to the succinctness of their representation
On measuring nondeterminism in regular languages
On the relation between ambiguity and nondeterminism in finite automata
Non-deterministic communication complexity with few witnesses
Nondeterministic communication with a limited number of advice bits
A comparison of two lower-bound methods for communication complexity
Communication complexity and parallel computing
Communication complexity
Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
Automata, Languages, and Machines
On the Power of Las Vegas II. Two-Way Finite Automata
Measures of Nondeterminism in Finite Automata
Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations
Translating Regular Expressions into Small epsilon-Free Nondeterministic Finite Automata
Communication complexity
Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)
Area-time complexity for VLSI
Some complexity questions related to distributive computing(Preliminary Report)
On notions of information transfer in VLSI circuits
Succinctness of descriptions of context-free, regular and finite languages.
A complexity theory for vlsi

--CTR
Martin Kutrib , Andreas Malcher, Context-dependent nondeterminism for pushdown automata, Theoretical Computer Science, v.376 n.1-2, p.101-111, May, 2007
Galina Jirskov, State complexity of some operations on binary regular languages, Theoretical Computer Science, v.330 n.2, p.287-298, 2 February 2005
nondeterminism;limited ambiguity;descriptional complexity;communication complexity;finite automata