On the Power of Finite Automata with both Nondeterministic and Probabilistic States.
We study finite automata with both nondeterministic and random states (npfa's).  We restrict our attention to those npfa's that accept their languages with a small probability of error and run in polynomial expected time.  Equivalently, we study Arthur--Merlin games where Arthur is limited to polynomial time and constant space.Dwork and Stockmeyer [SIAM J. Comput., 19 (1990), pp. 1011--1023] asked whether these npfa's accept only the regular languages (this was known if the automaton has only randomness or only nondeterminism).  We show that the answer is yes in the case of npfa's with a 1-way input head.  We also show that if L is a nonregular language, then either L or $\bar{L}$ is not accepted by any npfa with a 2-way input head.Toward this end, we define a new measure of the complexity of a language L, called its 1-tiling complexity. For each $n$, this is the number of tiles needed to cover the 1's in the "characteristic matrix" of L, namely, the binary matrix with a row and column for each string of length $\le n$, where entry [x,y]=1 if and only if the string $xy \in L$.  We show that a language has constant 1-tiling complexity if and only if it is regular, from which the result on 1-way input follows. Our main result regarding the general 2-way input tape follows by contrasting two bounds: an upper bound of polylog(n) on the 1-tiling complexity of every language computed by our model and a lower bound stating that the 1-tiling complexity of a nonregular language or its complement exceeds a function in $2^{\Omega (\sqrt{\log n})}$ infinitely often.The last lower bound follows by proving that the characteristic matrix of every nonregular language has rank n for infinitely many n. This is our main technical result, and its proof extends techniques of Frobenius and Iohvidov developed for Hankel matrices [Sitzungsber. der Knigl. Preuss. Akad. der Wiss., 1894, pp. 407--431], [Hankel and Toeplitz Matrices and Forms: Algebraic Theory, Birkhauser, Boston, 1982].
Introduction
The classical subset construction of Rabin and Scott [25] shows that finite state automata with
just nondeterministic states (nfa's) accept exactly the regular languages. Results of Rabin
[24], Dwork and Stockmeyer [7] and Kaneps and Freivalds [17] show that the same is true of
probabilistic finite state automata which run in polynomial expected time. Here and throughout
the paper, we restrict attention to automata which accept languages with error probability which
is some constant ffl less than 1=2.
However, there has been little previous work on finite state automata which have both
probabilistic and nondeterministic states. Such automata are equivalent to the Arthur-Merlin
games of Babai and Moran [3], restricted to constant space, with an unbounded number of
rounds of communication between Arthur and Merlin. In this paper, we refer to them as npfa's.
In the computation of an npfa, each transition from a probabilistic state is chosen randomly
according to the transition probabilities from that state, whereas from a nondeterministic state,
it is chosen so as to maximize the probability that an accepting state is eventually reached. We
let 1NPFA and 2NPFA-polytime denote the classes of languages accepted by npfa's which have a
1-way or a 2-way input head, respectively, and which run in polynomial expected time. Dwork
and Stockmeyer [8] asked whether 2NPFA-polytime is exactly the set of regular languages,
which we denote by Regular.
In this paper, we prove the following two results on npfa's.
Theorem 1.1
Theorem 1.2 If L is nonregular, then either L or -
L is not in 2NPFA-polytime.
Thus, we resolve the question of Dwork and Stockmeyer for npfa's with 1-way head, and
in the case of the 2-way head model, we reduce the question to that of deciding whether
2NPFA-polytime is closed under complement. Theorem 1.1 also holds even if the automaton
has universal, as well as nondeterministic and probabilistic states. Moreover, Theorem 1.2 holds
even for Arthur-Merlin games that use o(log log n) space.
In proving the two results, we introduce a new measure of the complexity of a language L
called its 1-tiling complexity. Tiling complexity arguments have been used previously to prove
lower bounds for communication complexity (see e.g. Yao [29]). With each language L ' \Sigma   ,
we associate an infinite binary matrix ML , whose rows and columns are labeled by the strings
of \Sigma   . Entry ML [x; y] is 1 if the string xy 2 L and is 0 otherwise. Denote by ML (n) the finite
submatrix of ML , indexed by strings of length - n. Then, the 1-tiling complexity of L (and of
the matrix ML (n)) is the minimum size of a set of 1-tiles of ML (n) such that every 1-valued
entry of ML (n) is in at least one 1-tile of the set. Here, a 1-tile is simply a submatrix (whose
rows and columns are not necessarily contiguous) in which all entries have value 1.
In Section 3, we prove the following theorems relating language acceptance of npfa's to tiling
complexity. The proofs of these theorems build on previous work of Dwork and Stockmeyer [8]
and Rabin [24].
Theorem [3.1] A language L is in 1NPFA only if the 1-tiling complexity of L is O(1).
Theorem [3.3] A language L is in 2NPFA-polytime only if the 1-tiling complexity of L is
bounded by a polynomial in log n.
What distinguishes our work on tiling is that we are interested in the problem of tiling the
matrices ML (n), which have distinctive structural properties. If L is a unary language, then
ML (n) is a matrix in which all entries along each diagonal from the top right to the bottom left
are equal. Such a matrix is known as a Hankel matrix. An elegant theory on properties of such
Hankel matrices has been developed [15], from which we obtain strong bounds on the rank of
ML (n) if L is unary. In the case that L is not a unary language, the pattern of 0's and 1's in
ML (n) is not as simple as in the unary case, although the matrix still has much structure. Our
main technical contribution, presented in Section 4, is to prove new lower bounds on the rank
of ML (n) when L is not unary. Our proof uses techniques of Frobenius and Iohvidov developed
for Hankel matrices.
Theorem [4.4] If L is nonregular, then the rank of ML (n) is at least n+ 1 infinitely often.
By applying results from communication complexity relating the rank of a matrix to its tiling
complexity, we can obtain a lower bound on the 1-tiling complexity of non-regular languages.
Theorem [4.5] If L is nonregular, then the 1-tiling complexity of either L or -
L exceeds a
function in
log n) infinitely often.
However, there are nonregular languages, even over a unary alphabet, with 1-tiling complexity
O(log n) (see Section 4). Thus the above lower bound on the 1-tiling complexity of L
or -
L does not always hold for L itself. A simpler theorem holds for regular languages.
Theorem [4.1] The 1-tiling complexity of L is O(1) if and only if L is regular.
By combining these theorems on the 1-tiling complexity of regular and non-regular languages
with the theorems relating 1-tiling complexity to acceptance by npfa's, our two main results
(Theorems 1.1 and 1.2) follow as immediate corollaries.
The rest of the paper is organized as follows. In Section 2, we define our model of the npfa,
and the tiling complexity of a language. We conclude that section with a discussion of related
work on probabilistic finite automata and Arthur-Merlin games. In Section 3, we present
Theorems 3.1 and 3.3, which relate membership of a language L in the classes 1NPFA and
2NPFA-polytime to the 1-tiling complexity of L. A similar theorem is presented for the class
2NPFA, in which the underlying automata are not restricted to run in polynomial expected time.
In Section 4, we present our bounds on the tiling complexity of both regular and nonregular
languages. Theorems 1.1 and 1.2 are immediate corollaries of the main results of Sections 3
and 4. Extensions of these results to alternating automata and to Turing machines with small
space are presented in Section 5. Conclusions and open problems are discussed in Section 6.
Preliminaries
We first define our npfa model in Section 2.1. This model includes as special cases the standard
models of nondeterministic and probabilistic finite state automata. In Section 2.2 we define our
notion of the tiling complexity of a language. Finally, in Section 2.3, we discuss previous work
on this and related models.
2.1 Computational Models and Language Classes
A two-way nondeterministic probabilistic finite automaton (2npfa) consists of a set of states Q,
an input alphabet \Sigma, and a transition function ffi, with the following properties. The states Q
are partitioned into three subsets: the nondeterministic states N , the probabilistic (or random)
states R, and the halting states H . H consists of two states: the accepting state q a and the
rejecting state q r . There is a distinguished state q 0 , called the initial state. There are two
special symbols
2 \Sigma, which are used to mark the left and right ends of the input string,
respectively.
The transition function ffi has the form
For each fixed q in R, the set of random states, and oe 2 (\Sigma [ f6 c; $g), the sum of ffi(q; oe; q
over all q 0 and d equals 1. The meaning of ffi in this case is that if the automaton is in state q
reading symbol oe, then with probability ffi(q; oe; q d) the automaton enters state q 0 and moves its
input head one symbol in direction d (left if stationary if 0). For each
fixed q in N , the set of nondeterministic states, and oe
all q 0 and d. The meaning of ffi in this case is that if the automaton is in state q reading symbol
oe, then the automaton nondeterministically chooses some q 0 and d such that ffi(q; oe; q
enters state q 0 and moves its input head one symbol in direction d. Once the automaton enters
state q a (resp. q r ), the input head moves repeatedly to the right until the right endmarker
is read, at which point the automaton halts. In other words, for q 2 fq a ; q r g, ffi(q; oe; q;
for all oe On a given input, the
automaton is started in the initial configuration, that is, in the initial state with the head at
the left end of the input. If the automaton halts in state q a on the input, we say that it accepts
the input, and if it halts in state q r , we say that it rejects the input.
Fix some input string
strategy (or just strategy) on w is a function
such that ffi(q; oe; q oe. The meaning of Sw is that
if the automaton is in state q 2 N reading w j , then if Sw (q; the automaton enters
state q 0 and moves its input head one symbol in direction d. The strategy indicates which
nondeterministic choice should be made in each configuration.
A language L ' \Sigma   is accepted with bounded error probability if for some constant ffl ! 1=2,
1. for all w 2 L, there exists a strategy Sw on which the automaton accepts with probability
2. for all
2 L, on every strategy Sw , the automaton accepts with probability - ffl.
Language acceptance could be defined with respect to a more general type of strategy, in
which the nondeterministic choice made from the same configuration at different times may be
different. It is known (see [4, Theorem 2.6]) that if L is accepted by an npfa with respect to this
more general definition, then it is also accepted with respect to the definition above. Hence,
our results also hold for such generalized strategies.
A one-way nondeterministic probabilistic finite automaton (1npfa) is a 2npfa which can
never move its input head to the left; that is, ffi(q; oe; q Also, a
probabilistic finite automaton (pfa) and a nondeterministic finite automaton (nfa) are special
cases of an npfa in which there are no nondeterministic and no probabilistic states, respectively.
We denote by 1NPFA and 2NPFA the classes of languages accepted with bounded error
probability by 1npfa's and 2npfa's, respectively. If, on all inputs w and all nondeterministic
strategies, the 2npfa halts in polynomial expected time, we say that L is in the class 2NPFA-
polytime. The classes 1PFA, 2PFA and 2PFA-polytime are defined similarly, with pfa replacing
npfa. Finally, Regular denotes the class of regular languages.
Our model of the 2npfa is equivalent to an Arthur-Merlin game in which Arthur is a 2pfa, and
our classes 2NPFA and 2NPFA-polytime are identical to the classes AM(2pfa) and AM(ptime-
2pfa), respectively, of Dwork and Stockmeyer [8].
2.2 The Tiling Complexity of a Language
We adapt the notion of the tiling complexity of a function, used in communication complexity
theory, to obtain a new measure of the complexity of a language. Given a finite, two-dimensional
matrix M , a tile is a submatrix of M in which all entries have the same value. A tile is specified
by a pair (R; C) where R is a nonempty set of rows and C is a nonempty set of columns.
The entries in the tile are said to be covered by the tile. A tile is a b-tile if all entries of the
submatrix are b. A set of b-tiles is a b-tiling of M if every b-valued entry of M is covered by
at least one tile in the set. If M is a binary matrix, the union of a 0-tiling and a 1-tiling of M
is called a tiling of M . Let T (M) be the minimum size of a tiling of M . Let T 1 (M) be the
minimum size of a 1-tiling of M , and let T 0 (M) be the minimum size of a 0-tiling of M . Then,
Note that in these definitions it is permitted for tiles of the same
type to overlap.
We can now define the tiling complexity of a language. Associated with a language L over
alphabet \Sigma is an infinite binary matrix ML . The rows and columns of ML are indexed (say,
in lexicographic order), by the strings in \Sigma   . Entry ML [x; only if xy 2 L. Let
L n be the strings of L of length - n. Let ML (n) be the finite submatrix of ML whose rows
and columns are indexed by the strings of length - n. The 1-tiling complexity of a language
L is defined to be the function T 1
Similarly, the 0-tiling complexity of L is
and the tiling complexity of L is
A tiling of a matrix M is disjoint if every entry [x; y] of M is covered by exactly one tile.
The disjoint tiling complexity of a matrix M , ~
is the minimum size of a disjoint tiling of
M . Also, the disjoint tiling complexity of a language, ~
(n), is ~
T(ML (n)).
Tilings are often used in proving lower bounds in communication complexity. Let f :
1g. The function f is represented by a matrix M f whose rows are indexed by
elements of X and whose columns are indexed by elements of Y , such that M f [x;
Let T f denote T(M f ). Suppose that two cooperating parties, P 1 and P 2 , get inputs x 2 X and
respectively, and want to compute f(x; y). They can do so by exchanging information
according to some protocol (precise definitions of legal protocols can be found in [13]). If
the protocol is deterministic, then the worst case number of bits that need to be exchanged
(that is, the deterministic communication complexity) is bounded below by log ~
If the
protocol is non-deterministic, then the lower bound is log T f [1]. Finally, if the object of the
non-deterministic protocol is only to verify that f(x; that is indeed the case), then
the lower bound on the number of bits exchanged is log T 1
f .
2.3 Related Work
Our work on npfa's builds on a rich literature on probabilistic finite state automata. Rabin [24]
was the first to consider probabilistic automata with bounded error probability. He showed that
However, with a 2-way input head, pfa's can recognize nonregular languages.
This was shown by Freivalds [10], who constructed a 2pfa for the language f0 n 1
Greenberg and Weiss [12] showed that exponential expected time is required by any 2pfa accepting
this language. Dwork and Stockmeyer [7] and independently Kaneps and Freivalds [17]
showed that in fact any 2pfa which recognizes a nonregular language must run in exponential
expected time. It follows that 2PFA-polytime = Regular.
Roughly, Rabin's proof shows that any language L accepted by a 1pfa has only finitely
many equivalence classes. Here, two strings x; x 0 are equivalent if and only if for all y, xy 2
L. The Myhill-Nerode theorem [14] states that a language has a finite number of
equivalence classes if and only if it is regular. This, combined with Rabin's result, implies that
decades later, this idea was extended to 2pfa's. A strengthened version
of the Myhill-Nerode theorem is needed for this extension. Given a language L, we say that
two strings x; x 0 are pairwise n-inequivalent if for some y, xy 2 L , x 0 y 62 L, and furthermore,
(the nonregularity of L) be size of the largest set of pairwise n-
inequivalent strings. Kaneps and Freivalds [16] showed that NL (n) - b(n + 3)=2c for infinitely
many n. (It is interesting to note that to prove their bound, Kaneps and Freivalds first showed
that NL (n) equals the number of states of the minimal deterministic 1-way finite automaton
that accepts all words of length - n that are in L and rejects all words of length - n that are
not in L. Following Karp [19], we denote the latter measure by OE L (n). Karp [19] previously
proved that OE L (n) infinitely many n. Combining this with the fact that NL (n)
and OE L (n) are equal, it follows immediately that NL (n) ? n=2+1 for infinitely many n. This is
stronger (by 1) for even n than Kaneps and Freivalds' lower bound. We also note that Dwork
and Stockmeyer [7] obtained a weaker bound on NL (n) without using OE L (n).) Using tools from
Markov chain theory, Dwork and Stockmeyer [7] and Kaneps and Freivalds [17] showed that
if a language is accepted by a 2pfa in polynomial expected time, then the language has "low"
nonregularity. In fact, NL (n) is bounded by some polynomial in log n. This, combined with
the result of Kaneps and Freivalds, implies that 2PFA-polytime = Regular.
Models of computation with both nondeterministic and probabilistic states have been studied
intensively since the work of Papadimitriou [23] on games against nature. Babai and Moran
[3] defined Arthur-Merlin games to be Turing machines with both nondeterministic and probabilistic
states, which accept their languages with bounded error probability. Their work on
polynomial time bounded Arthur-Merlin games laid the framework for the remarkable progress
on interactive proof systems and their applications (see for example [2] and the references
therein). Space bounded Arthur-Merlin games were first considered by Condon and Ladner
[6]. Condon [4] showed that AM(log-space), that is, the class of languages accepted by Arthur-
Merlin games with logarithmic space, is equal to the class P. However, it is not known whether
the class AM(log-space, polytime) - the subclass of AM(log-space) where the verifier is also
restricted to run in polynomial time - is equal to P, or whether it is closed under complement.
Fortnow and Lund [9] showed that NC is contained in AM(log-space,poly-time).
Dwork and Stockmeyer [8] were the first to consider npfa's, which are Arthur-Merlin games
restricted to constant space. They described conditions under which a language is not in the
classes 2NPFA or 2NPFA-polytime. The statements of our Theorems 3.2 and 3.3 generalize and
simplify the statements of their theorems, and our proofs build on theirs. In communication
complexity theory terms, their proofs roughly show that languages accepted by npfa's have low
"fooling set complexity". This measure is defined in a manner similar to the tiling complexity
of a language, based on the following definition. Define a 1-fooling set of a binary matrix A to
be a set of entries
The size of a 1-fooling set of a binary matrix is always at most the 1-tiling complexity of the
matrix, because no two distinct entries in the 1-fooling set, [x can be in the
same tile. However, the 1-tiling complexity may be significantly larger than the 1-fooling set
in fact, for a random n \Theta n binary matrix, the expected size of the largest 1-fooling
set is O(log n) whereas the expected number of tiles needed to tile the 1-entries is \Omega\Gamma n= log n)
3 NPFA's and Tiling
Three results are presented in this section. For each of the classes 1NPFA, 2NPFA and 2NPFA-
polytime, we describe upper bounds on the tiling complexity of the languages in these classes.
The proof for 1NPFA's is a natural generalization of Rabin's proof that
The other two proofs build on previous results of Dwork and Stockmeyer [8] on 2npfa's.
3.1 1NPFA and Tiling
Theorem 3.1 A language L is in 1NPFA only if the 1-tiling complexity of L is O(1).
Proof: Suppose L is accepted by some 1npfa M with error probability ffl ! 1=2. Let the
states of M be cg.
Consider the matrix ML . For each 1-entry [x; y] of ML , fix a nondeterministic strategy that
causes the string xy to be accepted with probability at least 1 \Gamma ffl. With respect to this strategy,
define two vectors of dimension c. Let p xy be the state probability vector at the step when the
input head moves off the right end of x. That is, the i'th entry of the vector is the probability of
being in state i at that moment, assuming that the automaton is started at the left end of the
input
6 cxy$ in the initial state. Let r xy be the column vector whose i'th entry is the probability
of accepting the string xy, assuming that the automaton is in state i at the moment that the
head moves off the right end of x. Then the probability of accepting the string xy is the inner
product
ffl)=c. Partition the space [0; 1] c into cells of size - \Theta - \Theta \Delta \Delta \Delta \Theta - (the final
entry in the cross product should actually be less than - if 1 is not a multiple of -). Associate
each 1-entry [x; y] with the cell containing the vector p xy ; we say that [x; y] belongs to this cell.
With each cell C, associate the rectangle RC defined as
fxj there exists y such that [x; y] belongs to Cg
\Theta
fyj there exists x such that [x; y] belongs to Cg:
This is the minimal submatrix that covers all of the entries associated with cell C.
We claim that RC is a valid 1-tile - that is, RC covers only 1-entries. To see this, suppose
. If [x; y] belongs to C, then it must be a 1-entry. Otherwise, there exist x 0 and y 0
such that [x; y 0 belong to C; that is, xy are in the same
cell.
We claim that xy is accepted with probability at least 1=2 on some strategy, namely the
strategy that while reading x, uses the strategy for xy 0 , and while reading y, uses the strategy
for x 0 y. To see this, note that
c
c
-c
our choice of -:
Hence, the probability that xy is accepted on the strategy described above is
Because xy is accepted with probability greater than ffl on this strategy, it cannot be that xy 62 L.
Hence, for all [x; y] 2 RC , xy must be in L. Therefore RC is a 1-tile in ML .
Every 1-entry [x; y] is associated with some cell C, and is covered by the 1-tile RC that is
associated with C. Thus, every 1-entry of ML is covered by some RC .
Hence L can be 1-tiled using one tile per cell, which is a total of d1=-e
3.2 2NPFA and Tiling
We next show that if L 2 2NPFA, then T 1
L (n) is bounded by a polynomial.
Theorem 3.2 A language L is in 2NPFA only if the 1-tiling complexity of L is bounded by a
polynomial in n.
Proof: Suppose L is accepted by some 2npfa M with error probability
c be the number of states of M . As in Theorem 3.1, for each 1-entry [x; y] of ML (n), fix a
nondeterministic strategy that causes M to accept the string xy with probability at least 1 \Gamma ffl.
We construct a stationary Markov chain H xy that models the computation of M on xy
using this strategy.
This Markov chain has states. 2c of the states are labeled (q; l), where q is a
state of M and l 2 f0; 1g. The other states are labeled Initial, Accept, Reject, and Loop. The
state (q; 0) of H xy corresponds to M being in state q while reading the rightmost symbol of
6 cx.
The state (q; 1) of H xy corresponds to M being in state q while reading the leftmost symbol of
y$. The state Initial corresponds to the initial configuration of M . The states Accept, Reject,
and Loop are sink states of H xy .
A single step of the Markov chain H xy corresponds to running M on input xy (using the
fixed nondeterministic strategy) from the appropriate configuration for one or more steps, until
M enters a configuration corresponding to one of the chain states (q; l). If M halts in the
accepting (resp., rejecting) state before entering one of these configurations, H xy enters the
Accept (resp., Reject) state. If M does not halt and never again reads the rightmost symbol of
6 cx or the leftmost symbol of y$, then H xy enters the Loop state. The transition probabilities
are defined accordingly.
Consider the transition matrix of H xy . Collect the rows corresponding to the chain states
Initial and (q; 0) (for all q) and call this submatrix P xy . Collect the rows corresponding to the
chain states (q; 1) and call this submatrix R xy . Then the transition matrix looks like this:
R xy
Initial
Accept
Reject
Loop
where I 3 denotes the identity matrix of size 3. (We shall engage in a slight abuse of notation
by using H xy to refer both to the transition matrix and to the Markov chain itself.) Note that
the entries of P xy depend only on x and the nondeterministic strategy used; these transition
probabilities do not depend on y. This assertion appears to be contradicted by the fact that
our choice of nondeterministic strategy may depend on y; however, the idea here is that if we
replace y with y 0 while maintaining the same nondeterministic strategy we used for xy, then
will be identical to P xy , because the transitions involved simulate computation of M on
the left part of its input only. Similarly, R xy depends only on y and the strategy, and not on x.
We now show that if jxj - n and if p is a nonzero element of P xy , then
a second Markov chain K(6 cx) with states of the form (q; l), where q is a state of M and
1. The chain state (q; l) with l - j6 cxj corresponds to M being in state q
scanning the l'th symbol of
6 cx. Transition probabilities from these states are obtained from the
transition probabilities of M in the obvious way. Chain states of the form (q; cxj + 1) are sink
states of K(6cx) and correspond to the head of M falling off the right end of
6 cx with M in state
q. Now consider a transition probability p in P xy . Suppose that, in the Markov chain H xy , p
is the transition probability from (q; 0) to (q 0 ; 1). Then p 2 f0; 1=2; 1g, since if H xy makes this
transition, it must be simulating a single computation step of M . Suppose p is the transition
probability from (q; 0) to (q 0 ; 0). If p ? 0, then there must be some path of nonzero probability
in K(6 cx) from state (q; cxj) to (q 0 ; cxj) that visits no state (q 00 ; cxj), and since K(6 cx) has at
most cn states that can be on this path, there must be such a path of length at most cn + 1.
Since 1/2 is the smallest nonzero transition probability of M , it follows that p - 2 \Gammacn\Gamma1 . The
cases where p is a transition probability from the Initial state are similar.
Similarly, if jyj - n and if r is a nonzero element of R xy , then r - 2 \Gammacn\Gamma1 .
Next we present a lemma which bounds the effect of small changes in the transition probabilities
of a Markov chain. This lemma is a slight restatement of a lemma of Greenberg and
Weiss [12]. This version is due to Dwork and Stockmeyer [8].
If k is a sink state of a Markov chain R, let a(k; R) denote the probability that R is
(eventually) trapped in state k when started in state 1. Let fi - 1. Say that two numbers r
and r 0 are fi-close if either (i)
chains
i;j=1 and R
are fi-close if r ij and r 0
are fi-close for all pairs
Lemma 3.1 Let R and R 0 be two s-state Markov chains which are fi-close, and let k be a sink
state of both R and R 0 . Then a(k; R) and a(k; R 0 ) are fi 2s -close.
The proof of this lemma is based on the Markov chain tree theorem of Leighton and Rivest
[20], and can be found in [8].
Our approach is to partition the 1-entries of ML (n) into equivalence classes, as in the proof
of Theorem 3.1, but this time we will make entries [x; y] and [x equivalent only if the
corresponding Markov chains H xy and H x 0 y 0 are fi-close, where fi will be chosen small enough
that we can use Lemma 3.1 to show that xy 0 and x 0 y are accepted with high probability by
combining the strategies for xy and x 0 y 0 .
If [x; y] is a 1-entry such that jxj - n and jyj - n, then for any nonzero p of P xy (or r of
R xy
By partitioning each coordinate interval into subintervals of length -, we divide
the space
into at most d(cn
cells, each of size at most - \Theta - \Theta \Delta \Delta \Delta -.
Partition the 1-entries in ML (n) into equivalence classes by making xy and x 0 y 0 equivalent
have the property that for each state transition, if p and p 0 are the respective
transition probabilities, either log p and log p 0 are in the same (size -) subinterval
of
Note that the number of equivalence classes is at most (d(cn
We claim that if - is chosen small enough, these equivalence classes induce a 1-tiling of
ML (n) of size at most the number of equivalence classes. As in Theorem 3.1, we associate with
each equivalence class C the rectangle RC defined by
fxjthere exists y such that [x; y] 2 Cg \Theta fyj there exists x such that [x; y] 2 Cg.
We claim that for each [x; y] in RC , xy 2 L. That is, all entries in the rectangle are 1, so
the rectangle forms a 1-tile. Let [x; y] be in RC . There must be some y 0 such that [x; y 0
and some x 0 such that [x 0 ; y] 2 C. Consider the associated Markov chains H xy 0 and H x 0 y , and
in particular, consider the transition submatrices P xy 0 and R x 0 y . The first is associated with a
particular nondeterministic strategy on x, namely one which assumes the input is xy 0 and tries
to cause xy 0 to be accepted with high probability. The second is associated with a particular
nondeterministic strategy on y, namely one which assumes the input is x 0 y and tries to cause x 0 y
to be accepted with high probability. The two matrices P xy 0 and R x 0 y taken together correspond
to a hybrid strategy on xy: while reading x, use the strategy for xy 0 , and while reading y, use
the strategy for x 0 y. We will argue that this hybrid strategy causes xy to be accepted with
probability - 1=2.
We construct a hybrid Markov chain H xy using P xy 0 and R x 0 y . This chain models the
computation of M on xy using the hybrid strategy.
Since the 1-entries [x; y 0 ] and [x 0 ; y] are in the same equivalence class C, it follows that if p
and p 0 are corresponding transition probabilities in the Markov chains H xy 0 and H x 0 y , then either
Therefore, H xy 0 and H x 0 y are 2 -close, and it immediately
follows that H xy is 2 -close to H xy 0 (and to H x 0 y ). Let a xy 0 be the probability that M accepts
input xy 0 on the strategy for xy 0 , and let a xy be the probability that M accepts input xy using
the hybrid strategy. Then a xy 0 (resp., a xy ) is exactly the probability that the Markov chain
eventually trapped in the Accept state, when started in the Initial state.
Now xy 0 2 L implies a xy are 2 -close, Lemma 3.1 implies that
a xy
a xy 0
which implies
a xy -
Since ffl and d are constants, and since ffl ! 1=2, we can choose - to be a constant so small
that a xy - 1=2. Therefore xy must be in L.
Since each 1-entry [x; y] is in some equivalence class, the matrix ML (n) can be 1-tiled using
at most (d(cn
tiles. Therefore,
Since c; d, and - are constants independent of n, this shows that T 1
L (n) is bounded by a
polynomial in n. 2
3.3 2NPFA-polytime and Tiling
We now show that if L 2 2NPFA-polytime, then T 1
L (n) is bounded by a polylog function.
Theorem 3.3 A language L is in 2NPFA-polytime only if the 1-tiling complexity of L is
bounded by a polynomial in log n.
Proof: Suppose L is accepted by some 2npfa M with error probability ffl ! 1=2 in expected
time at most t(n). Let c be the number of states of M . For each 1-entry [x; y] of ML (n), fix a
nondeterministic strategy that causes M to accept the string xy with probability at least 1 \Gamma ffl.
We construct the Markov chain H xy just as in Theorem 3.2.
Say that a probability p is small if p ! t(n) \Gamma2 ; otherwise, p is large. Note that if p is a large
transition probability, then dividing the 1-
entries of ML (n) into equivalence classes, make xy and x 0 y 0 equivalent if H xy and H x 0 y 0 have the
property that for each state transition, if p and p 0 are the respective transition probabilities,
either p and p 0 are both small, or log p and log p 0 are in the same (size -) subinterval of
This time the number of equivalence classes is at most (d2 log
Model the computation of M on inputs x 0 y, xy 0 , and xy by Markov chains H x 0 y , H xy 0 , and
H xy , respectively, as before.
If p and p 0 are corresponding transition probabilities in any two of these Markov chains, then
either p and p 0 are 2 -close or p and p 0 are both small. Let E x 0 y be the event that, when H x 0 y
is started in state Initial, it is trapped in state Accept or Reject before any transition labeled
with a small probability is taken; define E xy 0 and E xy similarly. Since M halts in expected
time at most t(n) on the inputs x 0 y, xy 0 , and xy, the probabilities of these events go to 1 as n
increases. Therefore, by changing all small probabilities to zero, we do not significantly change
the probabilities that H x 0 y , H xy 0 , and H xy enter the Accept state, provided that n is sufficiently
large. A formal justification of this argument can be found in Dwork and Stockmeyer [8].
After these changes, we can argue that
a xy -
and choose - so that a xy - 1=2, as before. It then follows that
(1)
for all sufficiently large n, establishing the result. 2
4 Bounds on the Tiling Complexity of Languages
In this section, we obtain several bounds on the tiling complexity of regular and nonregular
languages. In Section 4.1, we prove several elementary results. First, all regular languages have
constant tiling complexity. Second, the 1-tiling complexity of all nonregular languages is at least
log infinitely often. We also present an example of a (unary) non-regular language
which has 1-tiling complexity O(log n). In Section 4.2, we use a rank argument to show that for
all nonregular languages L, either L or its complement has "high" 1-tiling complexity infinitely
often.
4.1 Simple Bounds on the Tiling Complexity of Languages
The following lemma is useful in proving some of the theorems in this section. Its proof is
implicit in work of Melhorn and Schmidt [21]; we include it for completeness.
Lemma 4.1 Any binary matrix A that can be 1-tiled with m tiles has at most 2 m distinct rows.
Proof: Let A be a binary matrix that can be 1-tiled by m tiles fT
For each row r of A, let g. Suppose
r 1 and r 2 are rows such that I(r 1 We show that in this case, rows r 1 and r 2 are
identical. To see this, consider any column c of A. Suppose that entry [r 1 ; c] has value 1, and
is covered by some tile T
therefore r 2 2 R j and [r 2 ; c] is covered by tile T j . Hence entry [r must have value 1, since
T j is a 1-tile. Hence, if [r 1 ; c] has value 1, so does [r 2 ; c]. Similarly, if [r 2 ; c] has value 1, then
so does entry [r 1 ; c]. Therefore r 1 and r 2 are identical rows. Since there are only 2 m possible
values for I(r), A can have at most 2 m distinct rows. 2
Theorem 4.1 The 1-tiling complexity of L is O(1) if and only if L is regular.
Proof: By the Myhill-Nerode theorem [14, Theorem 3.6], L is regular if and only if ML
has a finite number of distinct rows.
Suppose L is regular. Then by the above fact there exists a constant k such that ML has
at most k distinct rows. Consider any (possibly infinite) set R of identical rows in ML . Let C b
be the set of columns which have bit b in the rows of R, for 1. Then the subset specified
by (R; C b ) is a b-tile and covers all the b-valued entries in the rows of R. It follows that the
1-valued entries of R can be covered by a single tile, and hence there is a 1-tiling of ML (n) of
size k. (Similarly, there is a 0-tiling of ML (n) of size k.)
Suppose L is not regular. Since L is not regular, ML has an infinite number of distinct rows.
It follows immediately from Lemma 4.1 that M cannot be tiled with any constant number of
tiles. 2
The above theorem uses the simple fact that the 1-tiling complexity
L (n) of a language L
is a lower bound on the number of distinct rows of ML (n). In fact, the number of distinct rows
of ML (n), for a language L, is closely related to a measure that has been previously studied by
many researchers. Dwork and Stockmeyer called this measure non-regularity, and denoted the
non-regularity of L by NL (n) [7]. NL (n) is the maximum size of a set of n-dissimilar strings of
L. Two strings, w and w 0 , are considered n-dissimilar if jwj - n and jw 0 j - n, and there exists
a string v such that jwvj - n, It is easy to show
that the number of distinct rows of ML (n) is between NL (n) and NL (2n). Previously, Kaneps
and Freivalds [16] showed that NL (n) is equal to the number of states of the minimal 1-way
deterministic finite state automaton which accepts a language L 0 for which L 0
is the set of strings of L of length - n.
Shallit [28] introduced a similar measure: the nondeterministic nonregularity of L, denoted
by NNL (n), is the minimal number of states of a 1-way nondeterministic finite automaton
which accepts a language L 0 for which L 0
In fact, it is not hard to show that
To see this, suppose that M is an automaton with NNL (2n) states, which accepts a language
We construct a 1-tiling of ML (n) with one tile T q per state q of M ,
where entry [x; y] is covered by T q if and only if there is an accepting path of M on xy which
enters state q as the head falls off the rightmost symbol of x. It is straightforward to verify the
set of tiles defined in this way is indeed a valid 1-tiling of ML (n). A similar argument was used
by Schmidt [27] to prove lower bounds on the number of states in an unambiguous nfa.
We next turn to simple lower bounds on the 1-tiling complexity of nonregular languages.
From Theorem 4.1, it is clear that if L is nonregular, then T 1
L (n) is unbounded. We now use
a known lower bound on the nonregularity of nonregular languages to prove a lower bound for
(n).
Theorem 4.2 If L is not regular, then T 1
infinitely many n.
Proof: Kaneps and Freivalds [16] proved that if L is not regular, then NL (n) - b(n+3)=2c
for infinitely many n. By the definition of NL (n), the matrix ML (n) must have at least NL (n)
distinct rows. Therefore, by Lemma 4.1, T 1
(n). The lemma follows immediately.We next present an example of a unary nonregular language, with 1-tiling complexity
O(log n). Thus, the lower bound of Theorem 4.2 is optimal to within a constant factor.
Theorem 4.3 Let L be the complement of the language fa 1-tiling
complexity O(logn).
Proof: We show that the 1-valued entries of ML (n) can be covered with O(log n) 1-tiles.
Let lg n denote blog 2 binary numbers, of length at
most lg n. Number the bits of these numbers from right to left, starting with 1, so that for
example . For any binary number q, lg q is the maximum index i such that
if q is equal to 2
1. The next fact follows easily.
only if for all j such that j - maxflg x; lg yg,
Roughly, we construct a 1-tiling of ML (n), corresponding to the following nondeterministic
communication protocol. The party P 1 guesses an index j and sends j and x j to P 2 . Also P 1
sends indicating whether or not j - lg x. If j - lg x, then P 2 checks that y
checks that j - lg y and that y or equivalently, that y In either case,
can conclude that y of ML (n) is 1. The number of bits sent from
2.
We now describe the 1-tiling corresponding to this protocol. It is the union of two sets of
tiles. The first set has one tile T j;b for each j; b such that lg n -
The second set of tiles has one tile S j;0 , for all j such that dlog ne - j - 1.
To see that all the 1's in the matrix are covered by one of these tiles, note that if entry
[a x ; a y ] of the matrix is 1, then by the Fact, there exists an index j such that j - maxflg x; lg yg
and either x y, and j is such that
covered by tile T j;0 . 2
The nondeterministic communication protocol in the above proof is a slight variation of a
simple (and previously known) protocol for the complement of the set distinctness problem. In
the set distinctness problem, the two parties each hold a subset of must
determine whether the subsets are distinct. In our application, the problem is to determine,
whether the subset of whose corresponding values in x are
0, is distinct from the subset of whose corresponding values in y are 1.
4.2 Lower Bounds on the Tiling Complexity of Nonregular Languages
In this section we prove that if a language L is nonregular, then the 1-tiling complexity of either
L or -
L is "high" infinitely often. To prove this, we first prove lower bounds on the rank of ML
when L is nonregular. We then apply theorems from communication complexity relating rank
to tiling complexity.
The proofs of the lower bounds on the rank of ML are heavily dependent on distinctive
structural properties of ML . Consider first the case where L is a unary language over the
alphabet fag. In this case, for all
It follows that for every n, ML (n) is such that its auxiliary
diagonal (the diagonal from the top right to the bottom left) consists of equal elements, as do
all diagonals parallel to that diagonal. An example is shown in Figure 1. Such matrices are
classically known as Hankel matrices, and have been extensively studied [15]. In fact, a direct
application of known results on the rank of Hankel matrices shows that if L is nonregular, then
infinitely often. This was first proved by Iohvidov (see [15, Theorem
11.3]), based on previous work of Frobenius [11].
ffl a 1 a 2 a 3 a 4 a 5 a 6
a
a
a
a
a

Figure

1: The Hankel matrix ML (6) for
If L is a non-unary language, then ML does not have the simple diagonal structure of a
Hankel matrix. Nevertheless, ML still has structural properties that we are able to exploit. In
fact, the term Hankel matrix has been extended from its classical meaning to refer to matrices
ML of non-unary languages (see [26]). In what follows, we generalize the results on the rank
of classical Hankel matrices, and prove that for any nonregular language L, over an arbitrary
alphabet, rank(ML (n))
4.2.1 Notation and basic facts
Let L be a language over an arbitrary alphabet, and let
Consider a row of M indexed by a string w. This row corresponds to strings that have the
prefix w. For any string s, row ws corresponds to strings with the prefix ws. Thus the entries
in row ws can be determined by looking at those entries in row w whose columns are indexed by
strings beginning with s (see Figure 2). In what follows, we consider this relationship between
the rows of M more formally.
Let M(n;m) denote the set of vectors (finite rows) of M which are indexed by strings x of
length - n and whose columns are indexed by strings of length - m. Let -
M(n; m) denote the
subset of vectors of M(n;m) which are indexed by strings x of length exactly n. If v 0 is row x
of M(n;m+ i), where i ? 0 and v is row x of M(n;m), then v 0 is called an extension of v.
Suppose s be a string over \Sigma of length - m (possibly the empty string,
ffl). Define split (s) (v) to be the subvector formed from v by selecting exactly those columns
whose labels have s as a prefix. Also, relabel the columns of split (s) (v) by removing the prefix
s. Note that split (ffl) v. Note also that if \Sigma is unary, say foeg, then split (oe) (v) is v with
the first column removed. Let jvj denote the dimension (number of entries) of vector v. If \Sigma is
binary and oe 2 \Sigma, then

Figure

2: The matrix M(3) for is a palindromeg. The bold entries in
row 110 are determined by the bold entries in row 11. The bold entries in row 110 comprise
split (0) (11) for M(2; 3).
More generally, if
c
Also, the vector v consists of the first entry (indexed by the empty string, ffl), plus an
"interleaving" of the entries of split (oe) (v), for each oe 2 \Sigma. More precisely, we have the following
Fact 4.1 Let
We generalize the definition of the split function to sets of vectors. If V is a set of vectors
in M(n;m), and jsj - m, let split g. Then we have the following.
Fact 4.2 [ jsj=i split
(a) -
In what follows, the vectors we consider are assumed to be elements of vector spaces over
an arbitrary field F (e.g. our proofs will hold if F is taken to be the field of rationals F). All
references to rank, span, and linear independence apply to vector spaces over F.
Lemma 4.2 Suppose that b and that
where the ff i are in the field F. Suppose that for 1
k is an extension in M(n;m+ 1)
of b k and that v 0 is an extension of v to the same length as the b 0
k .
Suppose also that for some it is the case that for all s of length i,
split
.
is a string of length - m. Consider a
string j 0 of length m+ 1. Let j
Also,
By the hypothesis of the lemma,
split
Putting the last three equalities together, v 0 [j
Let rank(M(n; m)) be the rank of the set of vectors M(n;m) and let span(M(n; m)) be the
vector space generated by the vectors in M(n;m). The next lemma follows immediately from
the definitions.
Lemma 4.3 If v 0 2 span(M(n; m)); m? 0 and
4.2.2 A Lower Bound on the Rank of M(n) when L is Nonregular
A trivial lower bound on the rank of M(n) is given by the following fact.
Fact 4.3 L is nonregular if and only if there is an infinite sequence of integers p r satisfying
This is easily shown using the Myhill-Nerode theorem. Clearly, such a sequence exists if
and only if the rank of M(n) (as n increases) is unbounded. Moreover, the rank of M(n) is
unbounded if and only if the number of distinct rows in M(n) is unbounded. The Myhill-Nerode
theorem states that the number of equivalence classes of L (equivalently, the number of distinct
rows of M) is finite if and only if L is regular. It follows that L is nonregular if and only if
the rank of M(n) is unbounded. This conclusion has already been noted (see Sections II.3 and
II.5 of the book by Salomaa and Soittola [26], which describes results from the literature on
rational power series and regular languages).
The above lower bound is very weak. In what follows, we significantly improve it by using
the special structure of M(n). Namely, we show that there is an infinite sequence of values
of n such that rank(M(n)) - n + 1. We define the first value of n in our sequence to be the
length of the shortest word in L (clearly this case). To construct the
remainder of the sequence, we show (in Lemma 4.5) that because L is nonregular, for any value
of n, there is some m - n such that rank(M(n
prove (in Lemma 4.6 and the proof of Theorem 4.4) that if n is such that rank(M(n)) - n+ 1,
and we choose the smallest m - n such that rank(M(n
in fact rank(M(m 2.
We begin with the following useful lemma.
Lemma 4.4 Let n - 0; m - 1. Suppose that M(n
Proof: By induction on i. The result is true by hypothesis of the lemma in the case
and that the lemma is true for
It follows from the induction hypothesis that if v 2 M(n
must also be the case that if v 2 M(n+
then It remains to consider the vectors in -
1). By
Fact 4.2 (a), each such vector v is of the form split (oe) (v 0 ), where
for some oe; 1. By the inductive hypothesis,
Then, by Fact 4.2 (b), all of the vectors in split (oe) (M(n; are in M(n+1;m \Gamma i+1).
Hence, Finally, by the hypothesis of the lemma, span(M(n
Corollary 4.1 For any n - 0, if rank(M(n+1;
r.
Proof: If n - p then M(p) is a submatrix of M(n; 2p) so the result follows trivially.
Otherwise, choose i so that n a submatrix of M(n
and hence by Lemma 4.4, the rows of M(p) are contained in span(M(n; p)). Thus again
The following lemma shows the existence of an m - n such that rank(M(n
Lemma 4.5 Let L be a nonregular language. Then for any n, there exists an m - n such that
Proof: Let r be the number of strings of length - n. Clearly, rank(M(n; m)) - r for all
m, since there are r rows in M(n;m). Let r as in Fact 4.3, that is,
Hence, by Corollary 4.1, it must be the case that rank(M(n
2p is one possible value of m that satisfies the lemma. 2
It remains to show that if n is such that rank(M(n)) - n+ 1, and m is the smallest number
such that m - n and rank(M(n+1; m+1)) ? rank(M(n; m+1)), then rank(M(m+1)) - m+2.
This is clearly true if for all
in this case rank(M(n; m+ 1)) - m+ 2. The difficult case is when there exist values of i such
that To help deal with this case, we prove the
following lemma.
Lemma 4.6 Suppose that the following properties hold:
2. m is the smallest number ? n such that M(n
3. i is a number in the range
Then, there is some vector in M(n+ i which is not in span(M(n;
is the extension of some
Then, we claim that for some s;
split Fact 4.2 (b), this is sufficient to prove the lemma.
Suppose to the contrary that for all s of length i, split
be a basis of M(n;m). Let fb 0
p g be an extension of this basis in
1). By Properties 1 and 2 of the lemma, v is in span(M(n; m)). Let
applying Fact 4.1, we see that for all s;
split
We want to show that for all s of length i,
split
It follows from this and from Lemma 4.2 that
contradicting the fact that v 0 62 span(M(n; m+ 1)).
Consider the vectors split
k ). These are in M(n+ Fact 4.2 (b). If
this is clearly in span(M(n; m+ 1))). If and by Property 2 of this
lemma, these vectors are in span(M(n; l be a basis for span(M(n;
and for 1 - k - l, let c 0
k be an extension in M(n;m . Clearly the set fc 0
l g
is also linearly independent, and since rank(M(n; set is
a basis for span(M(n;
split
Then, also
split
Also, since v 2 M(n m), from Fact 4.2 (b) it must be that the vectors split (s) (v) are
in M(n Hence, again by Property 2 of this lemma, and by Lemma 4.4, these
vectors are in span(M(n;
l is a basis for span(M(n; follows that there exists a unique sequence
of coefficients - l such that
split
Also, by combining Equation 2 with Equation 4, we see that
split
1;l
2;l
p;l c l ]:
Thus
p;k for all k 2
We claim
split
l
2;l
l
l ]:
We now justify the claim. By our initial assumption, split
Thus for some unique coefficients - 0
l ,
split
l c 0
Each c 0
k is an extension of c k , and there is a unique linear combination of c l that
is equal to split (s) (v). It follows that each - 0
This proves the claim.
Combining the claim with Equation 3 yields
split
as desired. 2
We now prove the lower bound.
Theorem 4.4 If L is nonregular, then
Proof: The base case is n such that the shortest word in the language is of length n.
Suppose that rank(M(n)) - fixed n. Let m be the smallest number - n
such that rank(M(n there is such an m. We
claim that rank(M(m 2.
the claim is clearly true. Suppose m ? n.
be a basis for M(n; k), n - k - m+ 1, where the extensions of all vectors in B k are
in B k+1 . Let B 0
denote the subset of B k which are extensions of vectors in B k\Gamma1 .
We construct a set of m linearly independent vectors in M(m + 1) as follows. For k
from n to m+ 1, we define a linearly independent set C k of vectors in M(m+ 1; k), of size at
least k + 1. Then, Cm+1 is the desired set.
Let C . This is by definition a linearly independent set, and it has size - n
because (by our initial assumption) rank(M(n)) - n + 1. Suppose that n -
that C k is already constructed and is linearly independent. Construct C k+1 as follows.
k be the set of extensions in M(m+ of the vectors in C k . Add C 0
k to C k+1 .
to C k+1 . (Thus, C k+1 is expanded to contain those vectors in B k+1 which
are not in B 0
.)
(iii) Finally, suppose nothing is added to C k+1 in step (ii); that is, rank(M(n;
is such that then this is equivalent to: rank(M(n;
Thus, we can apply Lemma 4.6 to obtain a vector v
which is not in span(M(n; but is not in
k ).) Add v 0 to C k+1 .
We claim that the vectors in C k+1 are linearly independent. Clearly the set C 0
k is linearly
independent. Consider each vector u 0 added to C k+1 , which is not in C 0
k . By the construction,
u 0 is not in span(B 0
be the extension of vector u in M(m+ 1; k). We claim that the
vector u must be linearly dependent on the set B k . This is true if u 0 is added in step (ii), since
in this case u is in M(n; is a basis for M(n; k). It is also true in the case that u
the vector added in step (iii), since then by Lemma 4.4,
Hence, Moreover, u can be expressed as a unique linear
combination of the vectors of C k , with non-zero coefficients only on those vectors in B k .
If u 0 were in span(C 0
k ), then since it is an extension of u, it would also be expressible as a
unique linear combination of the vectors of C 0
k , with non-zero coefficients only on those vectors
in B 0
k . But that contradicts the fact that u 0 62 span(B 0
4.2.3 The Tiling Complexity Lower Bound
Theorem 4.5 If L is nonregular, then the 1-tiling complexity of either L or -
L is at leastp
log infinitely often.
Proof: Melhorn and Schmidt, and independently Orlin, showed that for any binary matrix
[21, 22]. Their result holds for A over any field. Halstenberg and Reischuk,
refining a proof of Aho et. al., showed that dlog ~
By Theorem 4.4, if L is nonregular, then the rank of M(n) is at least n
It follows that for infinitely many n,
log
5 Variations on the Model
In this section, we discuss extensions of our main results to other related models.
We first show that Theorem 1.1 also holds for the following "alternating probabilistic" finite
state automaton model. In this model, which we call a 2apfa, the nondeterministic states N
are partitioned into two subsets, NE and NU of existential and universal states, respectively.
Accordingly, for a fixed input, there are two types of strategy, defined as follows for a fixed
input string An existential (universal) strategy on w is a function
such that ffi(q; oe; q
A language L ' \Sigma   is accepted with bounded error probability if for some constant ffl ! 1=2,
1. for all w 2 L, there exists an existential strategy Ew on which the automaton accepts
with probability strategies Uw , and
2. for all
2 L, on every existential strategy Ew , the automaton accepts with probability
- ffl on some universal strategy Uw .
The complexity classes 1APFA, 1APFA-polytime, and so on, are defined in the natural way,
following our conventions for the npfa model.
Theorem 5.1
Proof: As in Theorems 1.1 and 3.1, we show that if L is a language accepted by a 1APFA,
then the tiling complexity of L is bounded. We first extend the notation of Theorem 3.1.
If E is an existential strategy on xy and U is a universal strategy on xy, let p xy (E; U) be
the state probability (row) vector at the step when the input head moves off the right end of x,
on the strategies E; U . Let r xy (E; U) be the column vector whose i'th entry is the probability
of accepting the string xy, assuming that the automaton is in state i at the moment that the
head moves off the right end of x, on the strategies E; U . For each 1-entry [x; y] of ML , fix an
existential strategy E xy , that causes xy to be accepted with probability at least 1 \Gamma ffl, for all
universal strategies.
Partition the space [0; 1] c into cells of size - \Theta - \Theta -, as before. Let C be a nonempty
subset of the cells. We say that entry [x; y] of ML belongs to C if xy 2 L, and C is the smallest
set of cells which contain all the vectors p xy strategies U .
With each nonempty subset C of the cells, associate a rectangle R C defined as follows.
fx j there exists y such that [x; y] belongs to Cg
\Theta
fy j there exists x such that [x; y] belongs to Cg:
R C is a valid 1-tile. To see this, suppose that [x; y] 2 R C . If [x; y] belongs to C, then
it must be a 1-entry. Otherwise, there exist x 0 and y 0 such that [x; y 0 belong to C.
Consider the strategy E that while reading x, uses the strategy E xy 0 , and while reading y,
uses the strategy E x 0 y . We claim that xy is accepted with probability at least 1=2 on existential
strategy E and any universal strategy U on xy. The probability that xy is accepted on strategies
E; U is
belong to the same set of cells C, are in
the same cell, for some universal strategy U 0 . Moreover,
This is because this quantity is the probability that x 0 y is accepted on existential strategy
and a universal strategy which is a hybrid of U and U 0 ; also by definition of E x 0 y , the probability
that x 0 y is accepted with respect to E x 0 y and any universal strategy is
-c
our choice of -:
Hence, the probability that xy is accepted on the strategies E; U is
Since U is arbitrary, it follows that there is an existential strategy E such that on all strategies
U , the probability that xy is accepted on the strategies E; U is greater than ffl, and so it cannot
be that xy 62 L. Hence, for all [x; y] 2 R C , xy must be in L. Therefore R C is a 1-tile in ML .
The proof is completed as in Theorem 3.1. 2
In the same way, Theorem 3.3 can also be extended to obtain the following.
Theorem 5.2 A language L is in 2APFA-polytime only if the 1-tiling complexity of L is
bounded by 2 polylog(n) .
Thus, for example, the language Pal, consisting of all strings over f0; 1g   which read the
same forwards as backwards, is not in the class 2APFA-polytime. To see this, consider the
submatrix of ML (n), consisting of all rows and columns labeled by strings of length exactly n.
This matrix contains a fooling set of size 2 n ; hence a 1-tiling of ML (n) requires at least 2 n tiles.
We next extend Theorem 1.2 to automata with o(log log n) space. We refer to these as
Arthur-Merlin games, since this is the usual notation for such automata which are not restricted
to a finite number of states [7]. The definition of an Arthur-Merlin game is similar to that of an
npfa, except that the machine has a fixed number of read/write worktapes. The Arthur-Merlin
game runs within space s(n) if on any input w with jwj - n, at most s(n) tape cells are used
on any worktape. Thus, the number of different configurations of the Arthur-Merlin game is
Theorem 5.3 Let M and -
M be Arthur-Merlin games which recognize a nonregular language L
and its complement -
L, respectively, within space o(log log n). Suppose that the expected running
time of both M and -
M is bounded by t(n). Then, for all b ! 1=2, log log t(n) - (log n) b . In
particular, t(n) is not bounded by any polynomial in n.
Proof: The proof of Theorem 1.2 can be extended to space bounded Arthur-Merlin games,
to yield the following generalization of Equation 1. Let c(n) be an upper bound on the number
of different configurations of M on inputs of length n, and let
sufficiently large n, the number of 1-tiles needed to cover ML (n) is at most
Since M uses o(log log n) space, for any constant c ? 0, d(n) - (log n) c , for sufficiently large n.
Now, suppose to the contrary that for some b ! 1=2, log log t(n) ! (log n) b for sufficiently
large n. Then,
log n):
Hence, the number of tiles needed to cover the 1-valued entries of ML (n) is 2 o(
log n) . The
same argument for -
M shows that also for for sufficiently large n, the number of tiles needed to
cover the 1-valued entries of M- L (n) is 2 o(
log n) .
Hence, by Theorem 4.5 L must be regular, contradiction. 2
Finally, we consider a restriction of the 2npfa model, which, given polynomial time, can only
recognize regular languages. A restricted 2npfa is a 2npfa for which there is some ffl ! 1=2 such
that on all inputs w and strategies Sw , the probability that the automaton accepts is either
Theorem 5.4 Any language accepted by a restricted 2npfa with bounded error probability in
polynomial time is regular.
Proof: Let L be accepted by a 2npfa M with bounded error probability in polynomial
expected time. Let \Sigma be the alphabet, ffi the transition function, the set
of states and N ae Q the set of nondeterministic states of M . Without loss of generality, let
g.
We first define a representation of strategies as strings over a finite alphabet. Let \Sigma
loss of generality, assume that \Sigma"\Sigma string S
corresponds to a strategy on
6 cw$, where
is of the
and
to be the set of strings of the form oe each oe i is in the
alphabet \Sigma, each S i is in the alphabet \Sigma 0 , and furthermore, corresponds to
a strategy of M on input causes w to be accepted.
Then, L 0 is accepted by a 2pfa with bounded error probability in polynomial time. Thus,
L 0 is regular [7]. Moreover, note that a string of the form is in L if and only
if for some choice of S 0 is in L 0 . Let M 0 be a one-way
deterministic finite state automaton for L 0 , and assume without loss of generality that the set
of states in which M 0 can be when the head is at an even position, is disjoint from the set of
states in which M 0 can be when the head is at an odd position. Then, from M 0 we can construct
a one-way nondeterministic finite state automaton for L, by replacing the even position states
by nondeterministic states. Hence, L is regular. 2
6 Conclusions
We have introduced a new measure of the complexity of a language, namely its tiling complexity,
and have proved a gap between the tiling complexity of regular and nonregular languages. We
have applied these results to prove limits on the power of finite state automata with both
probabilistic and nondeterministic states.
An intriguing question left open by this work is whether the class 2NPFA-polytime is closed
under complement. If it is, we can conclude that 2NPFA-polytime = Regular. Recall that the
class 2NPFA does contain nonregular languages, since it contains the class 2PFA, and Freivalds
[10] showed that f0 n 1 is in this class. However, Kaneps [18] showed that the class
2PFA does not contain any nonregular unary language. Another open question is whether
the class 2NPFA contains any nonregular unary language. It is also open whether there is a
nonregular language in 2APFA-polytime.
There are several other interesting open problems. Can one obtain a better lower bound on
the tiling complexity of nonregular languages than that given by Theorem 4.5, perhaps by an
argument that is not based on rank? We know of no nonregular language with tiling complexity
less
n) infinitely often, so the current gap is wide.



--R

On notions of information transfer in VLSI circuits
Proof verification and hardness of approximation problems

Computational Models of Games
On the Power of finite automata with both nondeterministic and probabilistic states
Probabilistic game automata

Finite state verifiers I: the power of interaction
Interactive proof systems and alternating time-space complexity
Probabilistic two-way machines

A lower bound for probabilistic algorithms for finite state machines
On different modes of communication
Introduction to Automata Theory
Hankel and Toeplitz Matrices and Forms: Algebraic Theory
Minimal nontrivial space complexity of probabilistic one-way Turing machines
Running Time to Recognize Nonregular Languages by 2- Way Probabilistic Automata
Regularity of one-letter languages acceptable by 2-way finite probabilistic au- tomata
Some bounds on the storage requirements of sequential machines and Turing machines
The Markov chain tree theorem
Las Vegas is better than determinism in VLSI and distributed computing
Contentment in Graph Theory: Covering Graphs with Cliques.
Games against nature
Probabilistic automata
Finite automata and their decision problems

Succinctness of description of context free
Automaticity: properties of a measure of descriptional complexity
Some complexity questions related to distributed computing
Lower bounds by probabilistic arguments
--TR

--CTR
Lutz Schrder , Paulo Mateus, Universal aspects of probabilistic automata, Mathematical Structures in Computer Science, v.12 n.4, p.481-512, August 2002
Bala Ravikumar, On some variations of two-way probabilistic finite automata models, Theoretical Computer Science, v.376 n.1-2, p.127-136, May, 2007
nondeterministic probabilistic finite automata;interactive proof systems;matrix tiling;hankel matrices;arthur-merlin games