The number of languages with maximum state complexity

Abstract

Câmpeanu and Ho (2004) determined the maximum finite state complexity of finite languages, building on work of Champarnaud and Pin (1989). They stated that it is very difficult to determine the number of maximum-complexity languages. Here we give a formula for this number. We also generalize their work from languages to functions on finite sets.

1 Introduction

At some point in the 1980s, Howard Straubing posed a problem that was subsequently solved in Champarnaud and Pin [2]. They showed that the minimal incomplete deterministic finite automaton of a language $L\subseteq \Sigma ^n$, where $\Sigma =\{0,1\}$, has at most

$$\begin{aligned} \sum _{i=0}^n \min (2^i, 2^{2^{n-i}}-1) \end{aligned}$$

states. Moreover, for each n there exists an L attaining this bound. Câmpeanu and Ho [1] showed more generally that the tight upper bound for $\Sigma$ of cardinality k and for complete automata is

$$\begin{aligned} \frac{k^r-1}{k-1} + \sum _{j=0}^{n-r}(2^{k^j}-1) + 1 \end{aligned}$$

where $r=\min \{m:k^m\ge 2^{k^{n-m}}-1\}$. (In these results, requiring totality of the transition function adds 1 to the state count.) Câmpeanu and Ho’s result can be viewed as concerning functions $f:[k]^n\rightarrow [2]$ where $[k]=\{0,\dots ,k-1\}$ is a set of cardinality k. We generalize their result to arbitrary functions $f:[k]^n\rightarrow [c]$ where c is a positive integer. Equivalently, we consider functions $f:[k]^*\rightarrow [c]$, where $\{x:f(x)>0\}\subseteq [k]^n$ for some n, and where automata have $c-1$ accept states corresponding to nonzero values of f.

The function $+$ on $\mathbb Z/5\mathbb Z$ may seem rather complicated as functions on that set go. On the other hand, $f(x,y,z)=x+y+z$ mod 5 is less so, in that we can decompose it as $(x+y)+z$, so that after seeing x and y, we need not remember the pair (x, y), but only their sum. Out of the $5^{5^3}$ ternary functions on a 5-element set, at most $5^{2\cdot 5^2}$ can be decomposed as $(x*_1y)*_2 z$ for some binary functions $*_1$, $*_2$. This idea of the state complexity of functions has been applied in bioinformatics [5]. In Section 2 we make precise a sense in which such functions are not the most complex ternary functions. We do this by extending a result of Câmpeanu and Ho [1] to functions taking values in a set of size larger than two. Rising to an implicit challenge posed by Câmpeanu and Ho, we give a formula for the number of maximally complex languages.

The structure of the paper is as follows. In Section 2 we obtain an upper bound in Theorem 2.14 for the complexity of a function $f:[b]^n\rightarrow [c]$, and a matching lower bound in Theorem 2.18. In Section 3 we obtain the number of maximal complexity functions in Theorem 3.10. Then we look at asymptotics in Section 4, culminating in Theorem 4.12.

2 Complexity of languages and operations

Let $\lambda$ denote the empty word. Let the cardinality of a finite set A be denoted by $\#(A)$, and the length of a finite word w by $|w|$. We define a function $\mathbb {I}_A:B\rightarrow A\cup \{0\}$ for any sets $A\subseteq B$ with $0\not \in A$ by

$$\begin{aligned} \mathbb {I}_A(x)={\left\{ \begin{array}{ll}x &{}\text {if }x\in A,\\ 0 &{}\text {if }x\not \in A.\end{array}\right. } \end{aligned}$$

Definition 2.1

Let b and c be positive integers and let $\Sigma$ be an alphabet with $\#\left( \Sigma \right) =b$. An incomplete deterministic finite automaton (IDFA) M is a 5-tuple $(Q, \Sigma , \delta , q_0, F)$, where Q is a finite set of states, $\Sigma$ is a finite alphabet, $q_0 \in Q$ is the start state, $F\subseteq Q$ is the set of accept states, and $\delta : D \rightarrow Q$, where $D\subseteq Q\times \Sigma$, is the transition function.

W also require $F=\{1,\dots ,c-1\}=[c]\setminus \{0\}$, where $c-1=\#\left( F\right)$. If $D=Q\times \Sigma$, i.e., $\delta$ is total, then M is moreover a deterministic finite automaton (DFA).

We define ${\overline{\delta }}:D\rightarrow Q$, where $D\subseteq Q\times \Sigma ^*$, by ${\overline{\delta }}(q,\lambda )=q$, and recursively ${\overline{\delta }}(q,x u) = \delta ({\overline{\delta }}(q,x),u)$ for $x\in \Sigma ^*$ and $u\in \Sigma$. We say that states $q_1,q_2$ are M-distinguishable if there is a z with ${{\overline{\delta }}}(q_1,z)\ne {{\overline{\delta }}}(q_2,z)$ and $\{{{\overline{\delta }}}(q_1,z),{{\overline{\delta }}}(q_2,z)\}\cap F\ne \emptyset$.

The function accepted by M is the function $f:\Sigma ^*\rightarrow [c]$ defined by

$$\begin{aligned} f(x) = \mathbb {I}_F({\overline{\delta }}(q_0,x)),\quad \text { if } {\overline{\delta }}(q_0,x) \text { is defined }, \end{aligned}$$

and $f(x)=0$ otherwise. Thus $f(x)=0$ if ${\overline{\delta }}(q_0,x)\not \in F$, and $f(x)={\overline{\delta }}(q_0,x)$ if ${\overline{\delta }}(q_0,x)\in F$. The language accepted by M is

$$\begin{aligned} L(M)=\{x\in \Sigma ^*:f(x)>0\}=\{x\in \Sigma ^*:{{\overline{\delta }}}(q_0,x)\in F\}. \end{aligned}$$

Note that in the case $c=2$, accepting a language is equivalent to accepting its indicator (characteristic) function.

Definition 2.2

(State complexity). We call an IDFA $M=(Q,\Sigma ,\delta ,q_0,F)$ minimal (for L(M)) if $\#\left( Q\right) \le \#\left( Q'\right)$ for all IDFAs $M'=(Q',\Sigma ,\delta ',q_0',F')$ with $L(M')=L(M)$. Moreover, M is minimal for f if M accepts f and $\#\left( Q\right) \le \#\left( Q'\right)$ for all $M'$ accepting f. In this case we define the state complexity $\mathsf {sc}(f)$ by $\mathsf {sc}(f)=\#\left( Q\right)$.

Champarnaud and Pin [2] obtained the following result.

Theorem 2.3

[2, Theorem 4]. A minimal IDFA for a language $L\subseteq \{0,1\}^n$ has at most

$$\begin{aligned} \sum _{i=0}^n \min (2^i, 2^{2^{n-i}}-1) \end{aligned}$$

states,  and for each n there exists a language L attaining this bound.

Theorem 2.3 was generalized by Câmpeanu and Ho [1]:

Theorem 2.4

[1, Corollary 10]. Let $k\ge 1$ and $l\ge 0$ be integers,  and let M be a minimal DFA for a language $L\subseteq [k]^l$. Let Q be the set of states of M. Then we have : 

• (1) $\#\left( Q\right) \le \frac{k^r-1}{k-1}+\sum _{j=0}^{l-r} (2^{k^j}-1)+1,$ where $r=\min \{m\mid k^m\ge 2^{k^{l-m}}-1\}.$

• (2) There is an M such that the upper bound given by item 1 is attained.

Both of these results involve an upper bound which can be viewed as a special case of Theorem 2.14 below.

We now develop a function version of the Myhill–Nerode theorem, by following and generalizing the presentation in Shallit’s textbook [6].

Definition 2.5

Let $\Sigma$ be an alphabet and let $c\in \mathbb N$. A relation $R\subseteq \Sigma ^*\times \Sigma ^*$ is right invariant if for all $x,y,z\in \Sigma ^*$, we have $x R y\implies xz R yz$. An equivalence relation E on $\Sigma ^*$ is a congruence relation for $f:\Sigma ^*\rightarrow [c]$ if for all $x,y\in \Sigma ^*$, $xEy\implies f(x)=f(y).$ For an equivalence relation E, the index of E, denoted $\mathrm {index}(E)$, is the number of equivalence classes of E. An equivalence relation has finite index if $\mathrm {index}(E)<\infty$. The Myhill–Nerode equivalence relation for $f:\Sigma ^*\rightarrow [c]$ is the relation $R_f$ defined by

$$\begin{aligned} x R_f y\iff \text {for all }z\in \Sigma ^*, f(xz)=f(yz). \end{aligned}$$

Let $[x]_{f}$ denote the $R_{f}$-equivalence class of x.

Lemma 2.6

Let $f:\Sigma ^*\rightarrow [c]$.

• (1) $R_f$ is an equivalence relation.

• (2) $R_f$ right invariant.

Proof

item 1 is a standard observation. For item 2: If we extend xz and yz by the same string w, then we have also extended x and y by the same string zw, and hence $f(xzw)=f(yzw)$. $\square$

Lemma 2.7

Let $f:\Sigma ^*\rightarrow [c]$. Suppose that E is a right invariant equivalence relation on $\Sigma ^*$ which is a congruence relation for f. Then E is a refinement of $R_{f}$.

Proof

We must show that $xEy\implies x R_{f} y$. Suppose xEy and let $z\in \Sigma ^*$. Since E is right invariant, xzEyz. Since E is a congruence relation for f, $f(xz)=f(yz)$. Thus we have shown that $xR_{f} y$. $\square$

Every function is onto its range, and when the range is a finite subset of $\mathbb N$, when studying complexity under our definitions we assume the range is an initial segment of $\mathbb N$. Thus we restrict attention to onto functions in Theorem 2.8.

Theorem 2.8

Let $f:\Sigma ^*\rightarrow [c]$ be onto. The following are equivalent : 

• (1) f is accepted by some IDFA.

• (2) There exists a right invariant congruence relation for f of finite index.

• (3) $R_f$ has finite index.

• (4) f is accepted by some DFA.

Proof

We prove this in the usual round-robin fashion.

(1) $\implies$ (2): Let M be an IDFA that accepts f. Define a relation $R_M$ by $xR_M y$ iff ${{\overline{\delta }}}(q_0,x)={{\overline{\delta }}}(q_0,y)$, or both are undefined. Since M has finitely many states, $R_M$ has finite index. From the definition of ${{\overline{\delta }}}$ it follows that $R_M$ is right invariant. Finally, since $f(x)=\mathbb {I}_F({{\overline{\delta }}}(q_0,x))$ if defined, and 0 otherwise, f(x) is determined by ${{\overline{\delta }}}(q_0,x)$. Thus $R_M$ is a congruence relation for f.

(2) $\implies$ (3): Let R be a right invariant congruence relation for f, of finite index. By Theorem 2.7, R is a refinement of $R_f$. Then $\mathrm {index}(R_f)\le \mathrm {index}(R)<\infty$, as desired.

(3) $\implies$ (4): Suppose $R_f$ has finite index. Define $Q'=\{[x]_f:x\in \Sigma ^*\}$, $q_0'=[\lambda ]_f$, $F'=\{[x]_f: f(x)>0\}$, and $\delta '([x]_f,a)=[xa]_f$. Then $\#(Q')=\mathrm {index}(R_f)<\infty$. Since $R_f$ is right invariant, $\delta '$ is well-defined. Thus $M'=(Q',\Sigma ,\delta ',q_0',F')$ is an IDFA. We must show that $f(x)=\mathbb {I}_{F'}(\overline{\delta '}(q_0',x))$ for each x. Case 1: $f(x)=0$. Since $R_f$ is a congruence relation for f, $[x]_f\not \in F'$ and hence $\overline{\delta '}(q_0',x)=[\lambda x]_f=[x]_f\not \in F'$ which means that $\mathbb {I}_{F'}(\overline{\delta '}(q_0',x))=0$. Case 2: $f(x)>0$. Then by definition $[x]_f\in F'$ and so $\overline{\delta '}(q_0',x)=[\lambda x]_f=[x]_f\in F'$ which means that $\mathbb {I}_{F'}(\overline{\delta '}(q_0',x))=\overline{\delta '}(q_0',x)$. Finally, let $\pi :F'\rightarrow [c]\setminus \{0\}$ be a bijection and formally replace each $q\in F'$ by $\pi (q)\in [c]$.

(4) $\implies$ (1): This is immediate since each DFA is an IDFA.$\square$

Theorem 2.9

Let $f:\Sigma ^*\rightarrow [c]$. Let M be an IDFA accepting f. Let q be the number of states of M. Suppose that all states of M are reachable and that any two states of M are M-distinguishable. Then $\mathsf {sc}(f)=q$.

Proof

Let $M'$ be the automaton in Theorem 2.8 for f and let $Q'$ be its set of states. We claim that $M'$ is minimal. Note that $\#(Q')=\mathrm {index}(R_f)$. Let N be any automaton accepting f, let Q be its set of states and $\delta$ its transition function. Since N accepts f, for all x, y, z, if $f(xz)\ne f(yz)$ then ${{\overline{\delta }}}(q_0,x)\ne {{\overline{\delta }}}(q_0,y)$. Thus $[x]_f\mapsto {{\overline{\delta }}}(q_0,x)$ is injective, and we have established that $\mathrm {index}(R_f)\le \#(Q)$, and hence that $M'$ is minimal.

Now let $M=(Q,\Sigma ,\delta ,q_0,F)$ be any IDFA accepting f for which any two states are reachable and M-distinguishable. It suffices to show that $\#\left( Q\right) \le \#\left( Q'\right)$, and for this it suffices to give an injective map $\varphi :Q\rightarrow Q'$. For each $q\in Q$ we let

$$\begin{aligned} \varphi (q) = [x]_f\quad \text { where } x \text { is such that } {{\overline{\delta }}}(q_0,x)=q. \end{aligned}$$

(2.1)

Such an x must exist, or else q is not reachable.

Claim

$\varphi$ is well-defined by (2.1).

Proof of Claim

Suppose that ${{\overline{\delta }}}(q_0,y)=q$ and let us show $[x]_f=[y]_f$. Let $z\in \Sigma ^*$. Since M accepts f,

• for $i>0$, $f(xz)=i$ iff $\delta (q_0,xz)=i$ and $f(yz)=i$ iff $\delta (q_0,yz)=i$; and

• for $i=0$, $f(xz)=0$ iff $\delta (q_0,xz)$ is undefined or is not in F, and $f(yz)=0$ iff $\delta (q_0,yz)$ is undefined or is not in F.

We have

$$\begin{aligned} \delta (q_0,xz)=\delta (\delta (q_0,x),z)=\delta (q,z) =\delta (\delta (q_0,y),z)=\delta (q_0,yz) \end{aligned}$$

in the sense that $\delta (q_0,xz)$ and $\delta (q_0,yz)$ are both definitionally equal to $\delta (q,z)$, which may or may not be defined or in F. So in all cases $f(xz)=f(yz)$. $\square$

Finally, let us show that $\varphi$ is one-to-one. If $\varphi (q_1)=\varphi (q_2)$ then $[x_1]_f=[x_2]_f$ where $\delta (q_0,x_i)=q_i$. We will show, using M-distinguishability, that $q_1=q_2$.

Suppose $q_1\ne q_2$. Then there is some z with

$$\begin{aligned} \delta (q_0,x_1z)=\delta (q_1,z)\ne \delta (q_2,z)=\delta (q_0,x_2z) \end{aligned}$$

and $\{\delta (q_0,x_1z), \delta (q_0,x_2z)\}\cap F\ne \emptyset .$ Hence since M accepts f, $f(x_1z)\ne f(x_2 z)$, which contradicts $[x_1]_f=[x_2]_f$.$\square$

We write $A^B$ for the set of all functions from B to A.

Definition 2.10

Let b and c be positive integers and let ${[c]}^{{[b]}^n}$ be the set of n-ary functions $f:[b]^n\rightarrow [c]$. Let $\mathfrak C\subseteq {[c]}^{{[b]}^n}$. The Champarnaud–Pin family of ${\mathfrak {C}}$ is the family of sets $\{{\mathfrak {C}}_k\}_{0\le k\le n}$, where ${\mathfrak {C}}_k\subseteq {[c]}^{{[b]}^{n-k}}$, $0\le k\le n$, given by

$$\begin{aligned} {\mathfrak {C}}_k = \{g\in [c]^{[b]^{n-k}} : \exists f\in {\mathfrak {C}},\, w\in [b]^k\quad \forall x\quad g(x)=f(wx)\}. \end{aligned}$$

In terms of the function $\tau _w(x)=wx$, this can be restated as

$$\begin{aligned} {\mathfrak {C}}_k = \{f\circ \tau _w \in [c]^{[b]^{n-k}} : f\in \mathfrak C,\, w\in [b]^k\}. \end{aligned}$$

So ${\mathfrak {C}}_0={\mathfrak {C}}$, ${\mathfrak {C}}_1$ is obtained from ${\mathfrak {C}}_0$ by plugging in constants for the first input, and so forth. We write ${\mathfrak {C}}_n^-=\{f\in {\mathfrak {C}}_n: f(x)>0\text { for some } x\}$. Note that $\#\left( {\mathfrak {C}}_n^-\right) \ge \#\left( \mathfrak C_n\right) -1$.

Definition 2.11

Let us say that an IDFA M accepts $f:[b]^n\rightarrow [c]$ if M accepts the function $f^+:\Sigma ^*\rightarrow [c]$ with $f^+(x)=f(x)$ if $x\in [b]^n$, and $f^+(x)=0$ otherwise. The state complexity of $f:[b]^n\rightarrow [c]$ is the minimum number of states of an IDFA accepting $f:[b]^n\rightarrow [c]$, and is denoted $\mathsf {sc}(f)$.

Note that Theorem 2.11 says that $\mathsf {sc}(f)=\mathsf {sc}(f^+)$. For $c>b=2$, $\mathsf {sc}(f)$ corresponds to automatic complexity of equivalence relations on binary strings as studied in [3]. The case $b=c$ is that of n-ary operations on a given finite set, which is of interest in universal algebra.

We also define $\mathsf {maxsc}_{b,c,n}=\sum _{i=0}^n \min (b^i,c^{b^{n-i}}-1)$, which shall turn out to be the maximum of $\mathsf {sc}(f)$ over all f.

Definition 2.12

We define a crossover function $\chi (b,c,n)=\max \{i\in [0,n]\mid b^i\le c^{b^{n-i}}-1\}$.

Definition 2.13

Let $f\in [c]^{[b]^n}$ and $0\le j\le n$. We define an IDFA $M_{f,j}$. Its set of states is the disjoint union

$$\begin{aligned} Q = \{q_w: w\in [b]^i, i\le j\} \cup \{r_{g}: g\in {\mathfrak {C}}^-_i, i>j\}. \end{aligned}$$

where all $q_w$, $r_g$ are distinct. The transition function $\delta$ of $M_{f,j}$ is given by

$$\begin{aligned} \delta (q_w,a)= & {} {\left\{ \begin{array}{ll} q_{wa} &{} |w|<j, a\in [b], \\ r_{f\circ \tau _{wa}} &{} |w|=j, f\circ \tau _{wa}\not \equiv 0, \end{array}\right. }\\ \delta (r_g,a)= & {} r_{g\circ \tau _a}, \quad g\circ \tau _a\not \equiv 0. \end{aligned}$$

Theorem 2.14

Let b and c be positive integers. Let $f\in [c]^{[b]^n}$. Then $\mathsf {sc}(f)\le \mathsf {maxsc}_{b,c,n}.$

Proof

Let $f\in {\mathfrak {C}}$. We must show that there is an IDFA $M_f$ accepting f with at most the given number of states. Let $i_0=\chi (b,c,n)$ and let $M_f=M_{f,i_0}$ (Theorem 2.13). Then $\min (b^i,\#\left( {\mathfrak {C}}^-_{i}\right) )=b^i$ for $i\le i_0$ and $\min (b^i,\#\left( {\mathfrak {C}}^-_{i}\right) )=\#\left( {\mathfrak {C}}^-_i\right)$ for $i>i_0$. Note that for each $q\in Q$ there is an integer i(q) such that $i(q)\le i_0\implies q=q_w$ for some w and $i(q)>i_0\implies q=r_g$ for some g. The transition function $\delta$ is given by Theorem 2.13 and also described in Figure 1. Note that if $b^n + 1 < c$, we may not have $i_0 \le n$, but this is ruled out because then no $f:[b]^n\rightarrow [c]$ can be onto (Theorem 2.12). (We may assume that f is onto, since otherwise a smaller IDFA can be found.)

Fig. 1

Defining $\delta (q,a)$ in terms of $i=i(q)$ for Theorem 2.14

Since $f\in {\mathfrak {C}}$, we have

$$\begin{aligned} \#\left( \{f\circ \tau _w:w\in [b]^j\}\right) \le \#\left( \{h\circ \tau _w: w\in [b]^j, h\in {\mathfrak {C}}\}\right) \end{aligned}$$

although this need not be strict (for instance, when $j=n$, we are comparing the range of f to the union of ranges of h, $h\in {\mathfrak {C}}$, which may both equal [c]). By construction, $M_f$ accepts f; see also Example 2.15, Example 2.16, and Example 2.17. $\square$

Example 2.15

The following example shows the case $b=c=2$ and $n=3$, with f the majority function. It has $\chi (b,c,n)=1$:

The states $r_{g}$ for $g\in {\mathfrak {C}}^-_n\subseteq [c]\setminus \{0\}$ serve as our final states and are indicated by a rectangular box. Here $\top _k$ is the constant 1 function of k variables, whereas $1_j$ is defined by $1_j(x)=1$ if $j=x$, 0 otherwise. There is no arrow labeled 0 between the states $q_0$ and $r_{1_0}$. This is because after seeing $x=y=0$ we already know the majority of x, y, z is 0, so we “reject by missing transition”.

Example 2.16

A slightly larger example: the case $b=c=2$ and $n=4$, with f the majority function. It has $\chi (b,c,n)=2$:

In this case, the upper bound is strict: $q_{01}$ and $q_{10}$ are equivalent. Thus a smaller automaton suffices:

Example 2.17

As an example for the case $c>2$, let $b=2$, $c=3$, $n=2$, and let $f(x,y)=x+y$. Then our automaton $M_f$ is:

Theorem 2.18 is a generalization of Câmpeanu and Ho’s theorem. The construction is similar to that of [1, Figure 1 and Theorem 8].

Theorem 2.18

Let $b, c\ge 2$ and $n\ge 1$ be integers. There exists a function $f:[b]^n\rightarrow [c]$ such that $\mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}.$

Proof

Let ${\mathfrak {C}}=[c]^{[b]^n}$ To define $f\in {\mathfrak {C}}$, we first note that it suffices to fix an i with $0\le i\le n$ and define $f\circ \tau _w$ for each $w\in [b]^{i}$. To that end, we fix $i_0=\chi (b,c,n)$. Since

$$\begin{aligned} \#\left( [b]^{i_0}\right) = b^{i_0}\ge c^{b^{n-{i_0}}}-1 = \#\left( \mathfrak C_{i_0}^-\right) , \end{aligned}$$

there exists a surjective function $\phi :[b]^{i_0}\rightarrow \mathfrak C_{i_0}^-$. Define f by $f\circ \tau _w = \phi (w)$ for each $w\in [b]^{i_0}$. We claim that f attains the bound, i.e., there is no smaller automaton than that given in Theorem 2.14. By Theorem 2.9, an IDFA to accept f is minimal if all states are reachable (from the start state) and any two states are M-distinguishable.

Thus, it remains to show that the states for f as given in the proof of Theorem 2.14 are reachable and M-distinguishable.

By choice of $i_0$ it is easy to see that each state is reachable. For an example of what can go wrong with a different choice of $i_0$, see Figure 2.

As for distinguishability, all states have a path to an accepting state, so it suffices to show that states that are the same distance from the start state are M-distinguishable. Recall that the set of states of $M_f$ is

$$\begin{aligned} Q = \{q_w: w\in [b]^i, i\le i_0\} \cup \{r_{g}: g\in {\mathfrak {C}}^-_i, i>i_0\}. \end{aligned}$$

For two states $q_v$, $q_w$ where $|v|=|w|$, it suffices to consider the case $|w|=i_0$. Then $q_v$ and $q_w$ are M-distinguishable precisely because we chose $i_0$ and f so that each extension by adding one more symbol to v, w does not give the same set of possible extensions, i.e., precisely to distinguish v and w. Similarly $r_g$ and $r_h$ for $g,h\in {\mathfrak {C}}^-_i, i>i_0$ have the sets of possible extensions given by g, h and therefore are M-distinguishable. $\square$

Fig. 2

An unreachable state $\top _1$ in the automaton $M_{{\mathrm {XOR}},1}$ (Theorem 3.6)

3 The number of maximally complex languages

A k-set is a set of cardinality k. For a function $f:A\rightarrow B$ we denote the range and domain by ${{\,\mathrm{ran}\,}}(f)=\{f(x)\mid x\in A\}$ and ${{\,\mathrm{dom}\,}}(f)=A$, respectively. The collection of all subsets of A of cardinality k is denoted $\left( {\begin{array}{c}A\\ k\end{array}}\right)$.

Lemma 3.1

Let k, b, v, i be positive integers with $i<v$. Let $Z:b\rightarrow v$ be the constant function defined by $Z(b')=v-1$ for all $b'\in [b]$. The number of k-sets $X\subseteq [v]^{[b]}\setminus \{Z\}$ such that $\bigcup _{f\in X}{{\,\mathrm{ran}\,}}(f)\supseteq [i]$ is

$$\begin{aligned} \left( {\begin{array}{c} v^b -1\\ k\end{array}}\right) - \sum _{j=1}^i (-1)^{j+1} \left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}(v-j)^b-1\\ k\end{array}}\right) . \end{aligned}$$

(3.1)

Proof

There are $v^b-1$ elements of $[v]^{[b]}\setminus \{Z\}$ and hence $\left( {\begin{array}{c}v^b-1\\ k\end{array}}\right)$ total k-sets.

Since $i<v$, $v-1\not \in [i]=\{0,\dots ,i-1\}$. Thus the range of Z is disjoint from [i].

Given $J\subseteq [i]$, $\#\left( J\right) =j$, it follows that $Z\in ([v]\setminus J)^{[b]}$ and so there are $(v-j)^b-1$ functions in $[v]^{[b]}\setminus \{Z\}$ whose range is disjoint from J, i.e.,

$$\begin{aligned} \#\left( \left( [v]^{[b]}\setminus \{Z\}\right) \cap ([v]\setminus J)^{[b]}\right) =\#\left( ([v]\setminus J)^{[b]}\setminus \{Z\}\right) =(v-j)^b-1. \end{aligned}$$

Here $([v]\setminus J)^{[b]}\subseteq [v]^{[b]}$.

For the union of ranges to not contain [i] means that there is some $i'\in [i]$ that is missed. The number of k-sets that miss some $i'$ is then given by inclusion-exclusion in terms of j, the cardinality of a set $J\subseteq [i]$ that is disjoint from $\bigcup _{f\in X}{{\,\mathrm{ran}\,}}(f)$. Thus the number of k-sets with $\bigcup _{f\in X}{{\,\mathrm{ran}\,}}(f)\not \supseteq [i]$ is

$$\begin{aligned} \qquad \qquad \qquad \qquad \qquad \sum _{j=1}^i (-1)^{j+1} \left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}(v-j)^b-1\\ k\end{array}}\right) . \qquad \qquad \qquad \qquad \end{aligned}$$

$\square$

For fixed b and c, let ${\mathcal {B}}_d$ (${\mathcal {B}}_d^+$) be the set of all (not constant zero) functions from $[b]^d$ to [c].

Definition 3.2

For a function $f:[b]^n\rightarrow [c]$ and $0\le j\le n$, define a function $\varphi _{f,j}: [b]^j \rightarrow [c]^{[b]^{n-j}}$ by $\varphi _{f,j}(w) = f\circ \tau _{w}$ for all w.

Note that $\varphi _{f,j}$ is the function $\phi$ in the proof of Theorem 2.18.

Definition 3.3

For each $0\le j\le n$, let $Z_j:[b]^{n-j}\rightarrow [c]$ be the constant zero function. A set $X\subseteq [c]^{[b]^{n-j}}\setminus \{Z_j\}$ is j-adequate if

$$\begin{aligned} \{f\circ \tau _{a}\mid f\in X, a\in [b]\}\supseteq [c]^{[b]^{n-(j+1)}}\setminus \{Z_{j+1}\}. \end{aligned}$$

A function $\varphi : [b]^j \rightarrow [c]^{[b]^{n-j}}$ is called j-adequate if its range is a j-adequate $b^j$-set, i.e.:

• (1) $\varphi (w)\ne Z_{j}$ for each w,

• (2) $\varphi$ is injective, and

• (3) $\{(\varphi (w))\circ \tau _{a}\mid w\in [b]^{j}, a\in [b]\}\supseteq [c]^{[b]^{n-(j+1)}}\setminus \{Z_{j+1}\}.$

We say that $\varphi$ is adequate if it is j-adequate for $j=\chi (b,c,n)$.

Proposition 3.4

If $\varphi$ is j-adequate then $b^j\le c^{b^{n-j}}-1$ and $b^{j+1}\ge c^{b^{n-(j+1)}}-1$.

The proof of Theorem 3.4 is immediate. It follows that $\varphi$ can only be j-adequate if $j=\chi (b,c,n)$, unless we happen to have $b^{j+1}=c^{b^{n-(j+1)}}-1$.

Proposition 3.5

For all j,  we have $f=g\iff \varphi _{f,j}=\varphi _{g,j}$.

Proof

$\implies$ is immediate. Conversely, suppose $\varphi _{f,j}=\varphi _{g,j}$. Fix x and write $x=x_1x_2$, $|x_1|=j$. Then

$$\begin{aligned} f(x)=\varphi _{f,j}(x_1)(x_2)=\varphi _{g,j}(x_1)(x_2)=g(x). \end{aligned}$$

$\square$

Definition 3.6

For each f and j we defined the associated automaton $M_{f,j}$ in Theorem 2.13. Let $M^-_{f,j}$ be $M_{f,j}$ with unreachable states removed and indistinguishable states merged. Let $Q^-_{f,j}$ be the set of states of $M^-_{f,j}$.

Theorem 3.7

The following are equivalent : 

• (1) $\varphi _{f,\chi (b,c,n)}$ is adequate.

• (2) $\#(Q^-_{f,\chi (b,c,n)})=\mathsf {maxsc}_{b,c,n};$ all states of $Q^-_{f,\chi (b,c,n)}$ are reachable and distinguishable;  and $M^-_{f,\chi (b,c,n)}$ accepts f.

• (3) It is not the case that :  $\#(Q^-_{f,\chi (b,c,n)})<\mathsf {maxsc}_{b,c,n},$ and $M^-_{f,\chi (b,c,n)}$ accepts f.

Proof

(2) $\implies$ (1): If $\varphi _f$ is not adequate then by definition some states of $M_{f,\chi (b,c,n)}$ are not reachable.

(1) $\implies$ (2): Theorem 2.18.

(2) $\implies$ (3) is immediate.

(3) $\implies$ (2): Assume (3). Since $M^-_{f,\chi (b,c,n)}$ always accept f, it follows that it has $\ge \mathsf {maxsc}_{b,c,n}$ states. By Theorem 2.14 it has exactly $\mathsf {maxsc}_{b,c,n}$ states. $\square$

Theorem 3.8

The following are equivalent : 

• (1) $\varphi _{f,\chi (b,c,n)}$ is adequate.

• (2) $\mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}$.

Proof

(1) $\implies$ (2): by (1) $\implies$ (2) of Theorem 3.7 and then by Theorem 2.9.

(2) $\implies$ (1): Suppose $\lnot$(1). Then $\lnot$(1) in Theorem 3.7. Therefore $\lnot$(3) in Theorem 3.7, and so $\mathsf {sc}(f)<\mathsf {maxsc}_{b,c,n}$. $\square$

Proposition 3.9

Let b, c, n be given,  $i_0=\chi (b,c,n),$ $i=c^{b^{n-(i_0+1)}}-1,$ and $k=b^{i_0}$. The number of adequate functions $\varphi :[b]^{i_0}\rightarrow [c]^{[b]^{n-i_0}}$ is

(3.2)

Proof

If $\alpha _i$ is the number of adequate sets then the number of adequate functions $\varphi$ is $k!\,\alpha _i$.

The map $\varphi$ maps to functions whose union of ranges covers the next set of functions as in Theorem 3.1, k-sets $X=\{f_1,\dots ,f_k\}\subseteq [v]^{[b]}\setminus \{Z\}$ such that $\bigcup _{f\in X}{{\,\mathrm{ran}\,}}(f)\supseteq [i]$ where $i=c^{b^{n-(i_0+1)}}-1$.

Let $Z_0:[b]^{n-i_0}\rightarrow [c]$ be the constant zero function. Let $Z(a)=c^{b^{n-(i_0+1)}}-1$ for all a. Let

$$\begin{aligned} \beta : [c]^{[b]^{n-i_0}} \rightarrow {[c^{b^{n-(i_0+1)}}]}^{[b]} \end{aligned}$$

be an arbitrary bijection for which $\beta (Z_0)=Z$. By Theorem 3.1, applying $\beta$, and with $v=c^{b^d}$,

$$\begin{aligned} \alpha _i = \left( {\begin{array}{c}c^{b^{d+1}}-1\\ k\end{array}}\right) - \sum _{j=1}^i (-1)^{j+1} \left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}(c^{b^{d}}-j)^{b}-1\\ k\end{array}}\right) . \end{aligned}$$

Thus, the number of maps $\varphi$ is

$\square$

Theorem 3.10

Let integers $b,c\ge 2$ and $n\ge 1$ be given. Let $k=b^{j_0}$ where $j_0=\chi (b,c,n)$. Let $d+1=n-j_0$ and $i=c^{b^{d}}-1$. Then $\#\left( \{f\mid \mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}\}\right)$ is given by (3.2) and equals

Proof

By Theorem 3.5,

$$\begin{aligned} \#\{f:\mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}\}=\#\{\varphi _f:\mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}\}. \end{aligned}$$

By Theorem 3.8 this equals $\#\{\varphi _f: f\text { is adequate}\}$, which by Theorem 3.9 equals (3.2). $\square$

Example 3.11

For $n=4$ and $b=c=2$, we have $\chi (b,c,n)=2$, as illustrated in the following table:

i	0	1	2	3	4
$2^i$	1	2	4	8	16
$\#\left( {\mathcal {B}}_{n-i}^+\right) =2^{2^{n-i}}-1$	65535	255	15	3	1
$\min (2^i,2^{2^{n-i}}-1)$	1	2	4	3	1

determined by an injective function $\phi$ from $[2]^2$ to ${\mathcal {B}}_2^+$, such that $\bigcup \{{{\,\mathrm{ran}\,}}\phi (w)\mid w\in [2]^2\}\supseteq {\mathcal {B}}_1^+$. Associating each $\phi$ with the set $X_{\phi }=\{\phi (w)\mid w\in [2]^2\}\in \left( {\begin{array}{c}{\mathcal {B}}_2^+\\ 4\end{array}}\right)$, we see that the number of functions $\phi$ is 4! times the number of four-element subsets X of ${\mathcal {B}}_2^+$ for which $\bigcup \{{{\,\mathrm{ran}\,}}f\mid f\in X\}\supseteq {\mathcal {B}}_1^+$. By Theorem 3.1 that number is 1155: let $b=2$, $k=4$, $i=3$, and $v=2^2=4$ and calculate that (3.1) is $\left( {\begin{array}{c}15\\ 4\end{array}}\right) -3\left( {\begin{array}{c}8\\ 4\end{array}}\right) =1155$. Thus the total number of maximum complexity functions is $1155\cdot 24 = 27720$.

4 Asymptotics

In this section we demonstrate (Theorem 4.3) that while most functions do not have maximum complexity, the growth rate of the number of maximally complex functions is similar to that of the total number of function $f:[b]^n\rightarrow [c]$ for $b=c=2$.

Proposition 4.1

Suppose $i\le v$ and k are positive integers,  and A is a set. Suppose $(k-1)\#\left( A\right) <i$. Then we have

$$\begin{aligned}&\#\left( \{\varphi :[k]\rightarrow [v]^{A}\mid \bigcup _{t\in [k]} {{\,\mathrm{ran}\,}}(\varphi (t)) \supseteq [i] \}\right) \end{aligned}$$

(4.1)

$$\begin{aligned}= & {} k! \cdot \#\left( \{X\in \left( {\begin{array}{c}[v]^{A}\\ k\end{array}}\right) \mid \bigcup _{f\in X} {{\,\mathrm{ran}\,}}(f) \supseteq [i] \}\right) . \end{aligned}$$

(4.2)

Suppose that additionally $i<v$, and $Z:A\rightarrow [v]$ is a constant function with $Z(a)=z\not \in [i]$ for all $a\in A$. Then (4.1) also equals

$$\begin{aligned} k! \cdot \#\left( \left\{ X\in \left( {\begin{array}{c}[v]^{A}\\ k\end{array}}\right) \mid Z\not \in X, \bigcup _{f\in X} {{\,\mathrm{ran}\,}}(f) \supseteq [i] \right\} \right) . \end{aligned}$$

(4.3)

Proof

(4.1) = (4.2): Let $\varphi$ be given and let $X={{\,\mathrm{ran}\,}}(\varphi )$. It suffices to show that $\#\left( X\right) =k$. Since

$$\begin{aligned} \#\left( {{\,\mathrm{ran}\,}}(f)\right) \le \#\left( {{\,\mathrm{dom}\,}}(f)\right) =\#\left( A\right) \end{aligned}$$

for each $f\in X$, we have

$$\begin{aligned} i \le \#\left( \bigcup _{t\in [k]} {{\,\mathrm{ran}\,}}(\varphi (t))\right) = \#\left( \bigcup \{ {{\,\mathrm{ran}\,}}(f)\mid f\in X \} \right) \le \#\left( X\right) \#\left( A\right) . \end{aligned}$$

If $\#\left( X\right) \ne k$ then $\#\left( X\right) \le k-1$, and we have the contradiction

$$\begin{aligned} i\le \#\left( X\right) \#\left( A\right) \le (k-1)\#\left( A\right) < i. \end{aligned}$$

(4.4)

(4.1) = (4.3): When Z is constant equal to a value not in [i], $Z\not \in {{\,\mathrm{ran}\,}}(\varphi )$ follows from the other condition: if $Z\in {{\,\mathrm{ran}\,}}(\varphi )$ then let $X={{\,\mathrm{ran}\,}}(\varphi )\setminus \{Z\}$. Then $\#\left( X\right) =k-1$ and we get a contradiction as in (4.4). $\square$

Definition 4.2

Let b and c be positive integers and let $0\le t\le n$. Let $O_t=O_t^{(b,c,n)}$ be the number of functions from $[b^{t}]$ to $[c^{b^{n-t}}]$ that are onto $[c^{b^{n-t}}-1]$:

$$\begin{aligned} \forall y\in [c^{b^{n-t}}-1]\quad \exists x\in [b^t]\quad f(x)=y. \end{aligned}$$

Theorem 4.3

Let b and c be positive integers and let $n\ge 0$. Let $j_0=\chi (b,c,n)$. If the condition

$$\begin{aligned} b\cdot (b^{j_0}-1) < c^{b^{n-(j_0+1)}}-1 \end{aligned}$$

(4.5)

holds,  then $\#\left( \{f:[b]^n\rightarrow [c]\mid \mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}\}\right) =O_t,$ where $0\le t\le n$ is minimal such that $O_t>0$.

Proof

By Theorem 3.8,

$$\begin{aligned} \#\left( \{f\mid \mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}\}\right) =\#\left( \{f\mid \varphi _{f,\chi (b,c,n)}\text { is adequate}\}\right) . \end{aligned}$$

Let $Z_0:[b]^{n-j_0}\rightarrow [c]$ be the constant zero function. Let $Z(a)=c^{b^{n-(j_0+1)}}-1$ for all a. Let

$$\begin{aligned} \beta : [c]^{[b]^{n-j_0}} \rightarrow {[c^{b^{n-(j_0+1)}}]}^{[b]} \end{aligned}$$

be an arbitrary bijection for which $\beta (Z_0)=Z$.

Given $\varphi$ define $\psi$ by $\psi (x,b')=\varphi (x)\circ \tau _{b'}$. The following are equivalent:

• $\bigcup _{x\in [k]}{{\,\mathrm{ran}\,}}(\varphi (x))\supseteq [i]$;

• $\psi$ is onto [i].

Thus $O_t$ is equal to (4.1), where $t=\chi (b,c,n)+1$. By Theorem 4.1 under the bijection $\beta$, with $k=b^{j_0}$, $A=[b]$, $i=c^{b^{n-j_0}}-1$, and $v=c^{b^{n-j_0}}$, $O_t$ is moreover equal to (4.3), as desired. $\square$

Remark 4.4

The authors regret that in [4], the condition (4.5) in Theorem 4.3 was erroneously omitted. By definition $b^{j_0+1}>c^{b^{n-(j_0+1)}}-1$, so $b^{j_0+1}\ge c^{b^{n-(j_0+1)}}$, but the condition fails when $b^{j_0+1}\ge c^{b^{n-(j_0+1)}}+b-1$.

Example 4.5

Consider the case $n=1$, $b=c=2$ of Theorem 4.3. Then $i_0=1$, where $i_0$ is the least i such that $O_i>0$. $O_i^{(2,2,1)}$ is the number of functions from $[2^i]$ to $[2^{2^{1-i}}]$ that are onto $[2^{2^{1-i}}-1]$. For $i=0$, there are no such functions. For $i=1$, there are three such functions. And indeed, this is the number of maximal complexity functions in this case: the functions $f:\{0,1\}\rightarrow \{0,1\}$ that are onto $\{1\}$.

Definition 4.6

Let $O_{m,n}$ be the number of onto functions from [m] to [n]. Stirling numbers of the second kind are denoted and equal the number of equivalence relations on [m] with n equivalence classes.

The following result is well known.

Lemma 4.7

Let m, n be positive integers. Then

Lemma 4.8

Let u and v be positive integers. The number of functions from [u] to [v] that are onto the first $v-1$ elements of [v] is

The number of functions from [u] to [v] that are onto [i] is

Proof

Let m be the number of elements going to $[v]\setminus [i]$. Then we see that the number of such functions is

by Theorem 4.7. $\square$

Lemma 4.9

Let u be a positive integer. The number of functions from [u] to [u] that are onto $[u-1]$ is $(u+1)!/2$.

Proof

Note that for any m, and . By Theorem 4.8, the number of such functions is

$\square$

The following Theorem 4.10 will only be applied in the case $\gamma =0$.

Lemma 4.10

Let j be a nonnegative integer,  let $p\ge 2,$ and let $0\le \gamma \le j$ be an integer. Let $n=p^j+j-\gamma$ and $b=p,$ $c=p^{p^\gamma }$. $O_i:=O^{b,c,n}_i,$ where i is minimal such that $O_i>0,$ equals

$$\begin{aligned} \frac{(p^{p^j}+1)!}{2}. \end{aligned}$$

Proof

The condition that $O_i^{(b,c,n)}>0$ for some i, i.e., $b^i\ge c^{b^{n-i}}-1$ for some $0\le i\le n$, i.e., $p^i\ge p^{p^\gamma p^{n-i}}-1$, i.e., $p^n\ge p^{p^\gamma }-1$, i.e., either $n\ge p^\gamma$ (i.e., $\gamma \le j$) or $n=\gamma =0, p=2$, follows from $\gamma \le j$.

By Theorem 4.8, with $u=b^i, v=c^{b^{n-i}}$,

The condition $O_i>0$ is equivalent to $b^i\ge c^{b^{n-i}}-1$. When $b=c=p$ and $i>0$, this is equivalent to

$$\begin{aligned} i\ge p^\gamma p^{n-i} \end{aligned}$$

(4.6)

Let $k=p^{j}$. Since by assumption $n=k+j-\gamma$, (4.6) becomes

$$\begin{aligned} ip^{i} \ge p^\gamma p^n = kp^k \end{aligned}$$

Since the map $i\mapsto i p^i$ is increasing, the requirement for i is that $i\ge k$. Note that setting $i=k$ now makes $u=v$. Therefore by Theorem 4.9, $O_i$ is $(u+1)!/2=(p^i+1)!/2$ as desired. $\square$

Lemma 4.11

Let j be a nonnegative integer. Let $n=p^j+j$ and $b=c=p \ge 2$. Then

$$\begin{aligned} \#\left( \{f:[b]^n\rightarrow [c]\mid \mathsf {sc}(f)=\mathsf {maxsc}_{b,c,n}\}\right) = \frac{(p^{p^j}+1)!}{2}. \end{aligned}$$

Proof

We have $p^{n-j}=p^{p^j}$ and hence $p^{m}=p^{p^{n-m}}$ for $m=n-j$, so that $p^m > p^{p^{n-m}}-1$ but $p(p^{m-1}-1)< p^{p^{n-m}}-1$. Thus Theorem 4.3 applies and the number of such functions is $O_i:=O^{b,c,n}_i$, where i is minimal such that $O_i>0$. By Theorem 4.10 with $\gamma =0$ we are done. $\square$

Using Theorem 3.10 for $b=c=2$ we calculate some values for

$$\begin{aligned} {\mathrm {nmcf}}(n) = \#\{f:[2]^n\rightarrow [2]\mid \mathsf {sc}(f)=\mathsf {maxsc}_{2,2,n}\}, \end{aligned}$$

the number of maximally complex functions from $[2]^n$ to [2], in Table 1. (See also Figure 3) In Theorem 4.12 we shall study the limiting behavior suggested by Table 1.

Table 1 The number of maximally complex functions from $[2]^n$ to [2] for $n\le 6$

Theorem 4.12

The number of maximal complexity functions satisfies

$$\begin{aligned} \limsup _{n\rightarrow \infty }\frac{1}{n}\log _2\log _2({\mathrm {nmcf}}(n))=1. \end{aligned}$$

Proof

It is immediate that $\limsup _{n\rightarrow \infty }\frac{1}{n}\log _2\log _2({\mathrm {nmcf}}(n))\le 1$. For the other direction, consider the case where $n=2^j+j$ for some j. By Stirling’s approximation,

$$\begin{aligned} \log _2 (2^{2^j}!)= & {} 2^{2^j}\log _2 2^{2^j} - 2^{2^j} \log _2 e +O(\log _2 2^{2^j})\\= & {} 2^{2^j} 2^j - 2^{2^j} \log _2 e +O(2^j)\\= & {} 2^n - 2^{n-j} \log _2 e +O(2^j) \end{aligned}$$

and hence $\lim _{n\rightarrow \infty }\frac{1}{n}\log _2\log _2 (2^{2^{j}}!)=1$. By Theorem 4.11,

$$\begin{aligned} \limsup _{n\rightarrow \infty }\frac{1}{n}\log _2\log _2({\mathrm {nmcf}}(n))\ge 1. \end{aligned}$$

$\square$

In Theorem 4.11, $(p^{p^j}+1)!/2$ may seem like a large number but it is relatively small: in terms of $w:=p^k$,

$$\begin{aligned}&\frac{(p^{p^j}+1)!/2}{c^{b^n}}= \frac{(p^{p^j}+1)!/2}{p^{p^\gamma p^n}}\\&\quad =\frac{(p^{p^j}+1)!/2}{p^{p^{p^j+j}}} = \frac{(p^k+1)!/2}{p^{p^{k+j}}} = \frac{(p^k+1)!/2}{p^{k p^k}} = \frac{(w+1)!/2}{w^w}\rightarrow 0. \end{aligned}$$

Example 4.13

For $n=6$ and $b=c=2$, then, we get $i=k=2^j=4$, and

$$\begin{aligned} O_4^{2,2,6} = \frac{17!}{2} \end{aligned}$$

So there are more than 177 trillion maximum-complexity 6-ary Boolean functions, which is however a small fraction of the total number of such functions,

$$\begin{aligned} 2^{2^6} = 18,446,744,073,709,551,616 \end{aligned}$$

or over 18 quintillion.

Fig. 3

The $(2^{2^1}+1)!/2=60$ languages $Z=\{x\mid f(x)=1\}$ with maximal complexity, 7, for $n=3=2^1+1$ and $b=c=2$

Note

For future work, it would be interesting (but difficult) to determine the distribution of $\mathsf {sc}(f)$ over $f\in [c]^{[b]^n}$.