<p><strong>The bounds...</strong></p>

<p>We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber &amp; Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper.  </p>

<p><strong>...cannot be substantially improved</strong></p>

<p>There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof of the gap, is an adaptation of a similar example illustrating the limitations of 2-party protocols for proving lower bounds on nondeterministic state complexity from (Hromkovič et al. 2009):</p>

<p>We use the alphabet $[n]= \{\,1,2,\ldots,n\,\}$. Let $L=\{\,xyz\in [n]^3 \mid x=y \vee x\neq z \,\}$.</p>

<p>We first take care of $Cov(M)$. Observe that if $w=xyz$ with $y=z$, then
$w \in L$: in case $x=y$, $w\in L$ and in case $x\neq y$, we also have
$x\neq z$ and thus $w\in L$. Also, if $w$ is of the form $xyz$ with
$y\neq z$, then $w\in L$ iff $x\neq z$. So we can write $L = L'\cup L''$,
with $L'=\{xyz\in [n]^3 \mid y=z\}$ and $L''=\{\,xyz\in [n]^3 \mid y\neq z
\wedge x \neq z \,\}$.</p>

<p>Now consider the bipartite graphs $G' = (U',V',E')$ with $U'=[n]$, $V'=
\{yz \in [n]^2 \mid y=z\}$, $E' = U' \times V'$, as well
as $G'' = (U'',V'',E'')$ with $U''=[n]$, $V''= \{ yz \in [n]^2 \mid
y\neq z\}$,
$E'' = \{(x,yz) \mid x\neq z\}$, and $G = (U' \cup U'',V' \cup V'', E'\cup E'')$. 
Then a <a href="http://en.wikipedia.org/wiki/Bipartite_dimension">biclique edge cover</a> for the graph
$G$ gives rise to a covering of $M$ with $1$-monochromatic
submatrices, and vice versa (Theorem 21 in Gruber &amp; Holzer 2006). </p>

<p>A simple kernelization trick for computing a biclique edge cover for $G'$
is to put the twin vertices from $U'$ into equivalence classes. Then we do the same in the resulting graph for the twin vertices from $V'$.
Twin vertices are those with identical neighborhood.
This step does not alter the minimum number of bicliques needed to cover all
edges in the respective graph. </p>

<p>The kernelization step collapses $G'$ into a graph with two vertices and
a single edge. Thus, the edges of $G'$ can be covered with a single
biclique. Applying the kernelization step to $G''$ yields a <a href="http://en.wikipedia.org/wiki/Crown_graph">crown graph</a>
on $2n$ vertices, whose bipartite dimension (the minimum biclique edge
cover number) is <a href="http://en.wikipedia.org/wiki/Bipartite_dimension">known</a> to be $\sigma(n)$, where $\sigma$ is the inverse
function of the middle binomial coefficient (De Caen et al. 1981). Notice that $\sigma(n)=O(\log n)$.
Thus the bipartite dimension of $G$ is $1+\sigma(n)$, which is identical
to $Cov(M)$.</p>

<p>Now consider $Cov(N)$. Observe that if $w=xyz$ with $x=y$, then $w \in
L$. If $x\neq y$, then $x\in L$ iff $x\neq z$. So we can write $L = L'''
\cup L''''$
with $L'''=\{xyz\in [n]^3 \mid x=y\}$ and $L''''= \{xyz\in [n]^3 \mid
x\neq y \wedge x\neq z\}$. Almost the same argument as above yields
$Cov(N)=1+\sigma(n)$.</p>

<p>It remains to give a lower bound on the nondeterministic state
complexity of $L$. Observe that $L$ contains all words of the form $xxx$
with $x\in[n]$. For each such word $xxx$ fix an accepting computation of a minimal
NFA accepting $L$. Let $p_x$ denote the state reached after reading the
prefix $x$, and let $q_x$ denote the state reached after reading the
prefix $xx$ of the input word $xxx$. Then all pairs $(p_x,q_x)$ must be
different. For the sake of contradiction, assume $(p_x,q_x)=(p_y,q_y)$
for some $x\neq y$. Then we can construct an accepting computation
on input $xyx$, such that the NFA is in state $p_x=q_x$ after reading
the prefix $x$, and in state $q_y=q_x$ after reading the prefix $xy$.
But the string $xyx$ is not in $L$. For the state set $Q$ of the NFA, this shows
that $|Q|^2 \ge n$. Thus, 
for large $n$, we obtain a subexponential separation between $Cov(M)+Cov(N)$ and $|Q|$ (the nondeterministic state complexity of $L$).</p>

<p><strong>References</strong></p>

<ul>
<li><p>Dominique de Caen, David A. Gregory, Norman J. Pullman: The Boolean rank of zero-one matrices, in: Cadogan, Charles C. (ed.), 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173 (1981)</p></li>
<li><p>Hermann Gruber and Markus Holzer. <a href="http://eccc.hpi-web.de/report/2006/027/">Finding Lower Bounds for Nondeterministic State Complexity is Hard</a>. Report TR06-027, Electronic Colloquium on Computational Complexity (ECCC), March 2006. <a href="http://hermann-gruber.com/data/dlt06-submission.pdf">Short version</a> appeared in: Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of LNCS, pages 363-374. Springer, June 2006. </p></li>
<li><p>Juraj Hromkovic, Holger Petersen, Georg Schnitger: <a href="http://dx.doi.org/10.1016/j.tcs.2009.03.020">On the limits of the
communication complexity technique for proving lower bounds on the size
of minimal NFAs</a>. Theor. Comput. Sci. 410(30–32): 2972–2981 (2009)</p></li>
</ul>

CC BY-SA 3.0
2014-04-11T21:07:39.267Z
Nice, thank you! Now I have repaid you ;)
domotorp
CC BY-SA 3.0
2014-04-11T13:49:31.560Z
2014-04-13T21:43:41.757Z
2014-04-13T21:43:41.757Z
Hermann Gruber
<p>Related to a recent question (<a href="https://cstheory.stackexchange.com/questions/20468/bounds-on-the-size-of-the-smallest-nfa-for-l-k-distinct">Bounds on the size of the smallest NFA for L_k-distinct</a>) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from communication complexity bounds. What follows is a special version of that problem.</p>

<p>Suppose $L$ is a language over some $n$ letter alphabet whose words all have length $3$. Denote the size of the smallest NFA accepting $L$ by $NFA(L)$. Define an $n\times n^2$ matrix $M$ as $M(a;bc)=1$ if $abc\in L$ and otherwise $0$. Denote the minimal number of $1$-submatrices (submatrix that contains only $1$'s) covering all the $1$'s in matrix $M$ by $COV(M)$. (So $\log(COV(M))$ is the non-deterministic communication complexity of $M$.)
It is easy to see that $NFA(L)\ge COV(M)$. If we similarly define a matrix $N$ as $N(ab;c)=1$ if $abc\in L$ and otherwise $0$, then we also have $NFA(L)\ge COV(N)$.</p>

<p>Is there an $L$ for which $NFA(L)&gt;COV(M)+COV(N)?$</p>

<p>By what function of $COV(M)$ and $COV(N)$ can we upper bound $NFA(L)?$</p>

<fl.formal-languages><automata-theory><lower-bounds><communication-complexity><nfa>
Lower bound for NFA accepting 3 letter language
domotorp
# Lower bound for NFA accepting 3 letter language

(Asked by: username_0 on 2014-04-02)

Related to a recent question ([Bounds on the size of the smallest NFA for L\_k-distinct](https://cstheory.stackexchange.com/questions/20468/bounds-on-the-size-of-the-smallest-nfa-for-l-k-distinct)) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from communication complexity bounds. What follows is a special version of that problem.

Suppose $L$ is a language over some $n$ letter alphabet whose words all have length $3$. Denote the size of the smallest NFA accepting $L$ by $NFA(L)$. Define an $n\times n^2$ matrix $M$ as $M(a;bc)=1$ if $abc\in L$ and otherwise $0$. Denote the minimal number of $1$-submatrices (submatrix that contains only $1$'s) covering all the $1$'s in matrix $M$ by $COV(M)$. (So $\log(COV(M))$ is the non-deterministic communication complexity of $M$.)
It is easy to see that $NFA(L)\ge COV(M)$. If we similarly define a matrix $N$ as $N(ab;c)=1$ if $abc\in L$ and otherwise $0$, then we also have $NFA(L)\ge COV(N)$.

Is there an $L$ for which $NFA(L)>COV(M)+COV(N)?$

By what function of $COV(M)$ and $COV(N)$ can we upper bound $NFA(L)?$

**Tags:** fl.formal-languages, automata-theory, lower-bounds, communication-complexity, nfa

---

## 1 answers

### Answer by username_1 on 2014-04-11. Score: 12 | Accepted answer

**The bounds...**

We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper.

**...cannot be substantially improved**

There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof of the gap, is an adaptation of a similar example illustrating the limitations of 2-party protocols for proving lower bounds on nondeterministic state complexity from (Hromkovič et al. 2009):

We use the alphabet $[n]= \{\,1,2,\ldots,n\,\}$. Let $L=\{\,xyz\in [n]^3 \mid x=y \vee x\neq z \,\}$.

We first take care of $Cov(M)$. Observe that if $w=xyz$ with $y=z$, then
$w \in L$: in case $x=y$, $w\in L$ and in case $x\neq y$, we also have
$x\neq z$ and thus $w\in L$. Also, if $w$ is of the form $xyz$ with
$y\neq z$, then $w\in L$ iff $x\neq z$. So we can write $L = L'\cup L''$,
with $L'=\{xyz\in [n]^3 \mid y=z\}$ and $L''=\{\,xyz\in [n]^3 \mid y\neq z
\wedge x \neq z \,\}$.

Now consider the bipartite graphs $G' = (U',V',E')$ with $U'=[n]$, $V'=
\{yz \in [n]^2 \mid y=z\}$, $E' = U' \times V'$, as well
as $G'' = (U'',V'',E'')$ with $U''=[n]$, $V''= \{ yz \in [n]^2 \mid
y\neq z\}$,
$E'' = \{(x,yz) \mid x\neq z\}$, and $G = (U' \cup U'',V' \cup V'', E'\cup E'')$.
Then a [biclique edge cover](http://en.wikipedia.org/wiki/Bipartite_dimension) for the graph
$G$ gives rise to a covering of $M$ with $1$-monochromatic
submatrices, and vice versa (Theorem 21 in Gruber & Holzer 2006).

A simple kernelization trick for computing a biclique edge cover for $G'$
is to put the twin vertices from $U'$ into equivalence classes. Then we do the same in the resulting graph for the twin vertices from $V'$.
Twin vertices are those with identical neighborhood.
This step does not alter the minimum number of bicliques needed to cover all
edges in the respective graph.

The kernelization step collapses $G'$ into a graph with two vertices and
a single edge. Thus, the edges of $G'$ can be covered with a single
biclique. Applying the kernelization step to $G''$ yields a [crown graph](http://en.wikipedia.org/wiki/Crown_graph)
on $2n$ vertices, whose bipartite dimension (the minimum biclique edge
cover number) is [known](http://en.wikipedia.org/wiki/Bipartite_dimension) to be $\sigma(n)$, where $\sigma$ is the inverse
function of the middle binomial coefficient (De Caen et al. 1981). Notice that $\sigma(n)=O(\log n)$.
Thus the bipartite dimension of $G$ is $1+\sigma(n)$, which is identical
to $Cov(M)$.

Now consider $Cov(N)$. Observe that if $w=xyz$ with $x=y$, then $w \in
L$. If $x\neq y$, then $x\in L$ iff $x\neq z$. So we can write $L = L'''
\cup L''''$
with $L'''=\{xyz\in [n]^3 \mid x=y\}$ and $L''''= \{xyz\in [n]^3 \mid
x\neq y \wedge x\neq z\}$. Almost the same argument as above yields
$Cov(N)=1+\sigma(n)$.

It remains to give a lower bound on the nondeterministic state
complexity of $L$. Observe that $L$ contains all words of the form $xxx$
with $x\in[n]$. For each such word $xxx$ fix an accepting computation of a minimal
NFA accepting $L$. Let $p\_x$ denote the state reached after reading the
prefix $x$, and let $q\_x$ denote the state reached after reading the
prefix $xx$ of the input word $xxx$. Then all pairs $(p\_x,q\_x)$ must be
different. For the sake of contradiction, assume $(p\_x,q\_x)=(p\_y,q\_y)$
for some $x\neq y$. Then we can construct an accepting computation
on input $xyx$, such that the NFA is in state $p\_x=q\_x$ after reading
the prefix $x$, and in state $q\_y=q\_x$ after reading the prefix $xy$.
But the string $xyx$ is not in $L$. For the state set $Q$ of the NFA, this shows
that $|Q|^2 \ge n$. Thus,
for large $n$, we obtain a subexponential separation between $Cov(M)+Cov(N)$ and $|Q|$ (the nondeterministic state complexity of $L$).

**References**

* Dominique de Caen, David A. Gregory, Norman J. Pullman: The Boolean rank of zero-one matrices, in: Cadogan, Charles C. (ed.), 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173 (1981)
* Hermann Gruber and Markus Holzer. [Finding Lower Bounds for Nondeterministic State Complexity is Hard](http://eccc.hpi-web.de/report/2006/027/). Report TR06-027, Electronic Colloquium on Computational Complexity (ECCC), March 2006. [Short version](http://hermann-gruber.com/data/dlt06-submission.pdf) appeared in: Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of LNCS, pages 363-374. Springer, June 2006.
* Juraj Hromkovic, Holger Petersen, Georg Schnitger: [On the limits of the
  communication complexity technique for proving lower bounds on the size
  of minimal NFAs](http://dx.doi.org/10.1016/j.tcs.2009.03.020). Theor. Comput. Sci. 410(30–32): 2972–2981 (2009)

> **Comments:**
> **username_0**: Nice, thank you! Now I have repaid you ;)  

---

