Relationship between size of Boolean functions and DFAs

Question

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})$) ?

Answer 1

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 2

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 (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 (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 3

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. 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. 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 for the corrected bound.)

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

• Gregor Gramlich, Georg Schnitger: Minimizing NFAs and regular expressions. 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. 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. 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$.