<p>Regarding question 3:</p>
<p>There are <span class="math-container">$S^{2S} \cdot 2^S$</span> different DFAs on <span class="math-container">$S$</span> states (fixing the initial state), and so most Boolean functions require <span class="math-container">$\Omega(2^n/n)$</span> states. This is the same calculation as for Boolean circuits.</p>
<p>An explicit language which requires <span class="math-container">$\Omega(2^n/n)$</span> is the indexing language <span class="math-container">$\{ (x,i) : x_i = 1 \}$</span>, where <span class="math-container">$|x| = 2^{|i|}$</span>, which works out to <span class="math-container">$|x| \approx n - \log n$</span>. The DFA has to remember the first <span class="math-container">$|x|$</span> bits, which requires <span class="math-container">$2^{|x|} = \Theta(n/\log n)$</span> many states.</p>
<p>There are <span class="math-container">$2^{2^w}$</span> many languages of length <span class="math-container">$w$</span>, and each is accepted by a DFA of size <span class="math-container">$O(2^w)$</span>. Given a language on <span class="math-container">$n$</span> bits, construct a DFA which reads the first <span class="math-container">$n - w$</span> bits (size <span class="math-container">$O(2^{n-w})$</span>) and then transfers control to a DFA for the appropriate language on the remaining <span class="math-container">$w$</span> bits. The total size is <span class="math-container">$O(2^{n-w} + 2^{2^w})$</span>. Choosing <span class="math-container">$w = \log \log (2^n/n) \approx \log n$</span> gives a DFA of size <span class="math-container">$O(2^n/n)$</span> for every language on <span class="math-container">$n$</span> bits. This is the same construction as for Boolean circuits.</p>

CC BY-SA 4.0
2023-12-31T18:19:14.867Z
2023-12-31T18:19:14.867Z
Yuval Filmus
<p>Here are are my attempts to answer.  I'm not an expert on this subject.  Please check all details for yourself.</p>
<ol>
<li><p>No.  Consider <span class="math-container">$f$</span> defined by <span class="math-container">$f(x)=1$</span> iff <span class="math-container">$x_1 \ne x_{n/2+1}$</span> or <span class="math-container">$x_2 \ne x_{n/2+2}$</span> or ... or <span class="math-container">$x_{n/2} \ne x_n$</span>.  This has a polynomial-sized DNF:
<span class="math-container">$$(x_1 \land \neg x_{n/2+1}) \lor (\neg x_1 \land x_{n/2+1}) \lor  \cdots \lor (x_{n/2} \land \neg x_n) \lor (\neg x_{n/2} \land x_n).$$</span>
However, any DFA requires <span class="math-container">$2^{n/2}$</span> states (intuitively, after reading <span class="math-container">$x_1,\dots,x_{n/2}$</span>, the DFA must memorize that entire prefix of <span class="math-container">$x$</span>).</p>
</li>
<li><p>No.  The same counterexample works.</p>
</li>
<li><p>I don't know about <span class="math-container">$\Omega(2^n)$</span>, but the above demonstrates an example that requires <span class="math-container">$\Omega(2^{n/2})$</span> states, which is already exponential.  Another example of a function for which the minimal DFA has exponential size is multiplying two <span class="math-container">$n/2$</span> bit integers and outputting the middle bit.</p>
<p>I suspect a lower bound of <span class="math-container">$\Omega(2^n/n)$</span> is achievable, e.g., by treating the last <span class="math-container">$\lg n$</span> bits of <span class="math-container">$x$</span> as an index <span class="math-container">$i(x)$</span>, and then defining <span class="math-container">$f(x) = 1$</span> iff <span class="math-container">$1 \le i(x) \le n - \lg n$</span> and <span class="math-container">$x_i=1$</span> (intuitively, after reading <span class="math-container">$x_1,\dots,x_{n - \lg n}$</span>, I expect the DFA will need to memorize that entire prefix).</p>
</li>
</ol>
<hr />
<p>You might also be interested in:</p>
<ul>
<li><p>You might be interested in the complexity class <a href="https://en.wikipedia.org/wiki/L/poly" rel="nofollow noreferrer">L/poly</a> (non-uniform log-space).  It corresponds loosely to a (possibly cyclic) two-way DFA with polynomially many states, that has the option to read the bits of <span class="math-container">$x$</span> in any order, and to read them multiple times.</p>
</li>
<li><p>You might be interested in <a href="https://en.wikipedia.org/wiki/Binary_decision_diagram" rel="nofollow noreferrer">binary decision diagrams</a> (BDDs).  A BDD is basically an acyclic DFA for the language <span class="math-container">$L=\{x \mid f(x)=1\}$</span>, with the extra freedom that you can choose a variable ordering (an order in which <span class="math-container">$x_1,\dots,x_n$</span> are read by the DFA).  For some functions, the extra degree of freedom to choose an alternate variable ordering can allow an exponential reduction in the size of the BDD (compared to a DFA).</p>
</li>
</ul>

CC BY-SA 4.0
2023-12-31T06:30:38.053Z
2024-01-02T21:06:27.867Z
2024-01-02T21:06:27.867Z
D.W.
<p>Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes.</p>
<p><strong>Maximum and average state complexity</strong></p>
<ul>
<li><p><em>Jean-Marc Champarnaud, Jean-Eric Pin:
<a href="https://doi.org/10.1016/0166-218X(89)90037-1" rel="noreferrer">A maxmin problem on finite automata.</a> Discret. Appl. Math. 23(1): 91-96 (1989).</em> They describe those subsets of <span class="math-container">$\{0,1\}^n$</span> that require the maximum number of states when accepted by a DFA, i.e., subsets that have maximum deterministic state complexity, and also give the deterministic state complexity as a function <span class="math-container">$f(n)$</span>. Answering the OP's question 3., they show that <span class="math-container">$\lim\inf_{n\to \infty} n f(n) / 2^n = 1$</span> and the upper limit is at most twice as large, thus <span class="math-container">$f(n) = \Theta(2^n/n)$</span> and not in <span class="math-container">$\Omega(2^n)$</span>.</p>
</li>
<li><p><em>Hermann Gruber, Markus Holzer:
<a href="https://doi.org/10.1016/j.tcs.2007.07.035" rel="noreferrer">On the average state and transition complexity of finite languages.</a> Theor. Comput. Sci. 387(2): 155-166 (2007). Presented at DCFS 2006.</em> They (we) study the same as above, but for the average case - more importantly, state and transition complexity of NFAs is covered as well. (Beware that one of the bounds regarding NFAs has a small mistake; see <a href="https://arxiv.org/pdf/2001.02309.pdf" rel="noreferrer">here</a> for the corrected bound.)</p>
</li>
</ul>
<p><strong>polynomial-size DFAs - i.e. of size polynomial in <span class="math-container">$n$</span></strong></p>
<ul>
<li><p><em>Gregor Gramlich, Georg Schnitger:
<a href="https://doi.org/10.1016/j.jcss.2006.11.002" rel="noreferrer">Minimizing NFAs and regular expressions.</a> J. Comput. Syst. Sci. 73(6): 908-923 (2007). Presented at STACS 2005.</em> Under some cryptographic assumption, the class of polynomial-size DFAs accepting subsets of <span class="math-container">$\{0,1\}^n$</span> is highly nontrivial, in the sense that it contains strong pseudorandom function ensembles. More precisely, the cryptographic assumption is that nonuniform logspace contains strong pseudorandom generators. (I hope that I've reproduced the result correctly.) This technical result is then used to prove something about minimization problems for NFAs and regular expressions.</p>
</li>
<li><p><em>Hermann Gruber, Jan Johannsen:
<a href="https://doi.org/10.1007/978-3-540-78499-9_20" rel="noreferrer">Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.</a> FoSSaCS 2008: 273-286.</em> They (we) show that the class of polynomial-size DFAs accepting subsets of <span class="math-container">$\{0,1\}^n$</span> contains functions that require a) monotone formula size superpolynomial in <span class="math-container">$n$</span>, and b) monotone circuit depth in <span class="math-container">$\Omega(\log n^2)$</span> and c) regular expression size superpolynomial in <span class="math-container">$n$</span>.</p>
</li>
<li><p><em>Ehud Cseresnyes, Hannes Seiwert:
<a href="https://doi.org/10.1016/j.jcss.2021.10.004" rel="noreferrer">Regular expression length via arithmetic formula complexity.</a> J. Comput. Syst. Sci. 125: 1-24 (2022). Presented at DCFS 2020.</em> Among other things, they show that the binomial language <span class="math-container">$B_{n,k}$</span>, which contains all <span class="math-container">$n$</span>-bit strings with exactly <span class="math-container">$k$</span> ones, can be described by DFAs of size <span class="math-container">$O(n\cdot k)$</span> but require regular expression size superpolynomial in <span class="math-container">$k$</span>.</p>
</li>
</ul>

CC BY-SA 4.0
2024-01-02T20:46:32.150Z
2024-01-02T21:30:21.483Z
2024-01-02T21:30:21.483Z
Hermann Gruber
<p>Are there any works that study the relationship between Boolean functions and the size of the minimal DFAs required to represent those Boolean functions? Boolean functions refer to the usual definition, i.e., functions of the form <span class="math-container">$f: \{ 0, 1\}^n \rightarrow \{0, 1\}$</span>. The DFA representing a Boolean function <span class="math-container">$f$</span> only accepts strings <span class="math-container">$x \in \{ 0, 1\}^n$</span> of length exactly <span class="math-container">$n$</span> for which <span class="math-container">$f(x) =1$</span>. Hence, this primarily concerns the class of acyclic DFAs which only accept strings <span class="math-container">$X \subseteq \{0, 1\}^n$</span>.</p>
<p>The kind of questions I am interested to understand are the following,</p>
<ol>
<li>For any k-term DNF, is there a DFA of size poly(n, k) which can represent the DNF? In other words, is anything known about the relationship between the size of DNFs and the size of DFAs required to represent it?</li>
<li>If there is a Boolean formula over <span class="math-container">$n$</span> variables of size polynomial in <span class="math-container">$n$</span>, then does it imply that there exists an (acyclic) DFA which can represent the same function where the number of states in the DFA is bounded by polynomial in <span class="math-container">$n$</span>?</li>
<li>Is there any class <span class="math-container">$C$</span> of Boolean functions such that <span class="math-container">$|C| = 2^{p(n)}$</span> for which the size of minimal DFAs required to represent <span class="math-container">$c \in C$</span> has exponential number of states (<span class="math-container">$\Omega(2^{n})$</span>) ?</li>
</ol>

<fl.formal-languages><automata-theory><boolean-functions><dfa><boolean-formulas>
Relationship between size of Boolean functions and DFAs
Satwik
# Relationship between size of Boolean functions and DFAs

(Asked by: username_0 on 2023-12-31)

Are there any works that study the relationship between Boolean functions and the size of the minimal DFAs required to represent those Boolean functions? Boolean functions refer to the usual definition, i.e., functions of the form $f: \{ 0, 1\}^n \rightarrow \{0, 1\}$. The DFA representing a Boolean function $f$ only accepts strings $x \in \{ 0, 1\}^n$ of length exactly $n$ for which $f(x) =1$. Hence, this primarily concerns the class of acyclic DFAs which only accept strings $X \subseteq \{0, 1\}^n$.

The kind of questions I am interested to understand are the following,

1. For any k-term DNF, is there a DFA of size poly(n, k) which can represent the DNF? In other words, is anything known about the relationship between the size of DNFs and the size of DFAs required to represent it?
2. If there is a Boolean formula over $n$ variables of size polynomial in $n$, then does it imply that there exists an (acyclic) DFA which can represent the same function where the number of states in the DFA is bounded by polynomial in $n$?
3. Is there any class $C$ of Boolean functions such that $|C| = 2^{p(n)}$ for which the size of minimal DFAs required to represent $c \in C$ has exponential number of states ($\Omega(2^{n})$) ?

**Tags:** fl.formal-languages, automata-theory, boolean-functions, dfa, boolean-formulas

---

## 3 answers

### Answer by username_1 on 2023-12-31. Score: 5

Regarding question 3:

There are $S^{2S} \cdot 2^S$ different DFAs on $S$ states (fixing the initial state), and so most Boolean functions require $\Omega(2^n/n)$ states. This is the same calculation as for Boolean circuits.

An explicit language which requires $\Omega(2^n/n)$ is the indexing language $\{ (x,i) : x\_i = 1 \}$, where $|x| = 2^{|i|}$, which works out to $|x| \approx n - \log n$. The DFA has to remember the first $|x|$ bits, which requires $2^{|x|} = \Theta(n/\log n)$ many states.

There are $2^{2^w}$ many languages of length $w$, and each is accepted by a DFA of size $O(2^w)$. Given a language on $n$ bits, construct a DFA which reads the first $n - w$ bits (size $O(2^{n-w})$) and then transfers control to a DFA for the appropriate language on the remaining $w$ bits. The total size is $O(2^{n-w} + 2^{2^w})$. Choosing $w = \log \log (2^n/n) \approx \log n$ gives a DFA of size $O(2^n/n)$ for every language on $n$ bits. This is the same construction as for Boolean circuits.


---

### Answer by username_2 on 2023-12-31. Score: 5

Here are are my attempts to answer. I'm not an expert on this subject. Please check all details for yourself.

1. No. Consider $f$ defined by $f(x)=1$ iff $x\_1 \ne x\_{n/2+1}$ or $x\_2 \ne x\_{n/2+2}$ or ... or $x\_{n/2} \ne x\_n$. This has a polynomial-sized DNF:
   $$(x\_1 \land \neg x\_{n/2+1}) \lor (\neg x\_1 \land x\_{n/2+1}) \lor \cdots \lor (x\_{n/2} \land \neg x\_n) \lor (\neg x\_{n/2} \land x\_n).$$
   However, any DFA requires $2^{n/2}$ states (intuitively, after reading $x\_1,\dots,x\_{n/2}$, the DFA must memorize that entire prefix of $x$).
2. No. The same counterexample works.
3. I don't know about $\Omega(2^n)$, but the above demonstrates an example that requires $\Omega(2^{n/2})$ states, which is already exponential. Another example of a function for which the minimal DFA has exponential size is multiplying two $n/2$ bit integers and outputting the middle bit.

   I suspect a lower bound of $\Omega(2^n/n)$ is achievable, e.g., by treating the last $\lg n$ bits of $x$ as an index $i(x)$, and then defining $f(x) = 1$ iff $1 \le i(x) \le n - \lg n$ and $x\_i=1$ (intuitively, after reading $x\_1,\dots,x\_{n - \lg n}$, I expect the DFA will need to memorize that entire prefix).

---

You might also be interested in:

* You might be interested in the complexity class [L/poly](https://en.wikipedia.org/wiki/L/poly) (non-uniform log-space). It corresponds loosely to a (possibly cyclic) two-way DFA with polynomially many states, that has the option to read the bits of $x$ in any order, and to read them multiple times.
* You might be interested in [binary decision diagrams](https://en.wikipedia.org/wiki/Binary_decision_diagram) (BDDs). A BDD is basically an acyclic DFA for the language $L=\{x \mid f(x)=1\}$, with the extra freedom that you can choose a variable ordering (an order in which $x\_1,\dots,x\_n$ are read by the DFA). For some functions, the extra degree of freedom to choose an alternate variable ordering can allow an exponential reduction in the size of the BDD (compared to a DFA).


---

### Answer by username_3 on 2024-01-02. Score: 5

Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes.

**Maximum and average state complexity**

* *Jean-Marc Champarnaud, Jean-Eric Pin:
  [A maxmin problem on finite automata.](https://doi.org/10.1016/0166-218X(89)90037-1) Discret. Appl. Math. 23(1): 91-96 (1989).* They describe those subsets of $\{0,1\}^n$ that require the maximum number of states when accepted by a DFA, i.e., subsets that have maximum deterministic state complexity, and also give the deterministic state complexity as a function $f(n)$. Answering the OP's question 3., they show that $\lim\inf\_{n\to \infty} n f(n) / 2^n = 1$ and the upper limit is at most twice as large, thus $f(n) = \Theta(2^n/n)$ and not in $\Omega(2^n)$.
* *Hermann Gruber, Markus Holzer:
  [On the average state and transition complexity of finite languages.](https://doi.org/10.1016/j.tcs.2007.07.035) Theor. Comput. Sci. 387(2): 155-166 (2007). Presented at DCFS 2006.* They (we) study the same as above, but for the average case - more importantly, state and transition complexity of NFAs is covered as well. (Beware that one of the bounds regarding NFAs has a small mistake; see [here](https://arxiv.org/pdf/2001.02309.pdf) for the corrected bound.)

**polynomial-size DFAs - i.e. of size polynomial in $n$**

* *Gregor Gramlich, Georg Schnitger:
  [Minimizing NFAs and regular expressions.](https://doi.org/10.1016/j.jcss.2006.11.002) J. Comput. Syst. Sci. 73(6): 908-923 (2007). Presented at STACS 2005.* Under some cryptographic assumption, the class of polynomial-size DFAs accepting subsets of $\{0,1\}^n$ is highly nontrivial, in the sense that it contains strong pseudorandom function ensembles. More precisely, the cryptographic assumption is that nonuniform logspace contains strong pseudorandom generators. (I hope that I've reproduced the result correctly.) This technical result is then used to prove something about minimization problems for NFAs and regular expressions.
* *Hermann Gruber, Jan Johannsen:
  [Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.](https://doi.org/10.1007/978-3-540-78499-9_20) FoSSaCS 2008: 273-286.* They (we) show that the class of polynomial-size DFAs accepting subsets of $\{0,1\}^n$ contains functions that require a) monotone formula size superpolynomial in $n$, and b) monotone circuit depth in $\Omega(\log n^2)$ and c) regular expression size superpolynomial in $n$.
* *Ehud Cseresnyes, Hannes Seiwert:
  [Regular expression length via arithmetic formula complexity.](https://doi.org/10.1016/j.jcss.2021.10.004) J. Comput. Syst. Sci. 125: 1-24 (2022). Presented at DCFS 2020.* Among other things, they show that the binomial language $B\_{n,k}$, which contains all $n$-bit strings with exactly $k$ ones, can be described by DFAs of size $O(n\cdot k)$ but require regular expression size superpolynomial in $k$.


---

