The deterministic automaton complexity of a finite binary string \(x=x_1\ldots x_k\) is defined to be the least number \(A(x)\) of states of a finite state automaton \(M\) such that \(x\) is the only string of length \(k\) in the language accepted by \(M\). It was introduced by Shallit and Wang (2001).
In a Discrete Mathematics class in Spring 2009, students Jason Axelson, Chris Ho and Aaron Kondo wrote a C program that calculated the complexity of all strings of length at most 7.
Results:
\[A()=1,\quad A(0)=2,\]
\[A(x_1\ldots x_k)\le k \quad\text{ for } k\ge 2,\]
\[A(x_1\ldots x_k)\le k-1 \quad\text{ for } k\ge 5.\]
\[A(x)\le 5 \quad\text{ for } k=7.\]
The string \(011100\) is the only string (starting with a 0) of length 6 or less with the property that its complexity is increased when read backwards:
\[A(011100)=4\ne 5=A(001110).\]
A table of complexities is available:
Table of constants \(c\) with given property \(\forall x\in\{0,\dots,b-1\}^n\)
In the large-alphabet limit, Kayleigh graphs apply and we upper bound is \(\lfloor n/2\rfloor + 2\).
The example \(x=01\) shows the deterministic \(A(x)\) is not well defined unless
we also specify \(b\).
http://math.hawaii.edu/~bjoern/dfa-complexity-of-01-as-3-ary
Length \(n\) | \(b=1\), \(A(x)\le cn + 1\) | \(b=2\), \(A(x)\le cn\) | \(b=3\), \(A(x)\le cn\) | \(b=4\), \(A(x)\le cn\) |
---|---|---|---|---|
0 | 0 | \(\infty\) | \(\infty\) | \(\infty\) |
1 | 0 | 2 | 2 | 2 |
2 | 0 | 1 | 3/2? | 1 |
3 | 0 | 1 | 1 | 1 |
4 | 0 | 1 | 1 | 1 |
5 | 0 | 0.8 | 1 | 1 |
6 | 0 | 0.83 | in progress | |
7 | 0 | 0.714285 | ||
8 | 0 | 0.75 | ||
9 | 0 | 0.777 or 0.666 |
News (September 6, 2015): For binary strings of length at most 8, you may view witnessing automata using the format
http://math.hawaii.edu/~bjoern/dfa-complexity-of-011
Thus, the following table is now partially obsolete.
Complete table for binary strings of length \(\leq 7\) and partial table for length \(8\)
In the following table we only consider strings starting with 0, since strings starting with 1 have the same complexity as the string obtained by flipping each bit (e.g., \(K(001)=K(110)\)).
Some witnessing automata are linked to, they were drawn using svg-edit.
In the following table, \(\delta_i = 0102\) means that \((\delta(0,i),\delta(1,i),\delta(2,i),\delta(3,i)) = (0,1,0,2)\)
in a witnessing DFA with 4 states, found by the MATH 301 students’ program.
Curiously, note that below there are no instances of permutation automata (where \(\delta_i\) is a bijection) except for the empty string.
\(A^-(x)\) denotes incomplete DFA complexity, i.e., there is no requirement that the transition functions be total.
We have \(A_N(x)\le A^-(x)\le A(x).\)
String \(x\) | Complexity \(A(x)\) | \(\delta_0\) | \(\delta_1\) |
\(A^-(x)\) |
---|---|---|---|---|
1 | 0 | 0 | 1 | |
0 | 2 | 00 | 10 | 1 |
00 | 2 | 01 | 11 | 1 |
01 | 2 | 00 | 10 | 2 |
000 | 2 | 01 | 11 | 1 |
001 | 3 | 110 | 200 | 2 |
010 | 3 | 100 | 210 | 2 |
011 | 3 | 111 | 220 | 2 |
0000 | 2 | 01 | 11 | 1 |
0001 | 3 | 022 | 122 | 2 |
0010 | 4 | 1120 | 2321 | 3 |
0011 | 3 | 202 | 100 | 3 |
0100 | 4 | 1130 | 2211 | 3 |
0101 | 3 | 122 | 202 | 2 |
0110 | 4 | 1110 | 2231 | 3 |
0111 | 3 | 122 | 212 (avoids 0) | 2 |
00000 | 2 | 01 | 11 | |
00001 | 3 | 022 | 122 | |
00010 | 4 | 1120 | 2322 | |
00011 | 4 | 1122 | 2320 | |
00100 | 4 | 1102 | 2331 | |
00101 | 4 | 1132 | 2301 | |
00110 | 4 | 1101 | 2332 | |
00111 | 4 | 1131 | 2302 | |
01000 | 4 | 1302 | 2131 | |
01001 | 4 | 1223 | 2320 | |
01010 | 3 | 122 | 202 | |
01011 | 4 | 1221 | 2320 | |
01100 | 4 | 1001 | 2303 | |
01101 | 4 | 1322 | 2120 | |
01110 | 4 | 1220 | 2321 | |
01111 | 3 | 122 | 212 (avoids 0) | |
000000 | 2 | 01 | 11 | |
000001 | 3 | 022 | 122 | |
000010 | 4 | 0313 | 2333 | |
000011 | 4 | 0333 | 2313 | |
000100 | 5 | 11240 | 23221 | |
000101 | 5 | 11241 | 23220 | |
000110 | 5 | 11220 | 23241 | |
000111 | 4 | 2033 | 1002 | |
001000 | 5 | 13240 | 22211 | |
001001 | 4 | 1321 | 2220 | |
001010 | 4 | 2313 | 1233 (avoids 0) | |
001011 | 4 | 2032 | 1003 | |
001100 | 4 | 1320 | 2223 | |
001101 | 5 | 13241 | 22230 | |
001110 | 5 | 13220 | 22243 | 4 (\(A_N=3\)) |
001111 | 4 | 2313 | 3133 | |
010000 | 4 | 2133 | 3313 | |
010001 | 5 | 12243 | 23220 | |
010010 | 4 | 1220 | 2321 | |
010011 | 5 | 12231 | 23240 | |
010100 | 4 | 2313 | 1303 | |
010101 | 3 | 122 | 202 | |
010110 | 5 | 12210 | 23241 | |
010111 | 5 | 12211 | 23240 | |
011000 | 5 | 13240 | 21221 | |
011001 | 4 | 2002 | 1033 | |
011010 | 5 | 13220 | 21241 | |
011011 | 4 | 1221 | 2320 | |
011100 | 4 | 1220 | 2323 | |
011101 | 5 | 12241 | 23210 | |
011110 | 4 | 2313 | 1323 (avoids 0) | |
011111 | 3 | 122 | 212 | |
0000000 | 2 | |||
0000001 | 3 | |||
0000010 | 4 | |||
0000011 | 4 | |||
0000100 | 5 | |||
0000101 | 5 | |||
0000110 | 5 | |||
0000111 | 5 | |||
0001000 | 5 | |||
0001001 | 5 | |||
0001010 | 5 | |||
0001011 | 5 | |||
0001100 | 5 | |||
0001101 | 5 | |||
0001110 | 5 | |||
0001111 | 5 | |||
0010000 | 5 | |||
0010001 | 5 | |||
0010010 | 4 | |||
0010011 | 5 | |||
0010100 | 4 | |||
0010101 | 4 | |||
0010110 | 5 | |||
0010111 | 5 | |||
0011000 | 5 | |||
0011001 | 5 | |||
0011010 | 5 | |||
0011011 | 5 | |||
0011100 | 5 | |||
0011101 | 5 | |||
0011110 | 5 | |||
0011111 | 4 | |||
0100000 | 4 | |||
0100001 | 5 | |||
0100010 | 5 | |||
0100011 | 5 | |||
0100100 | 4 | |||
0100101 | 5 | |||
0100110 | 5 | |||
0100111 | 5 | |||
0101000 | 5 | |||
0101001 | 5 | |||
0101010 | 3 | |||
0101011 | 4 | |||
0101100 | 5 | |||
0101101 | 5 | |||
0101110 | 5 | |||
0101111 | 5 | |||
0110000 | 5 | |||
0110001 | 5 | |||
0110010 | 5 | |||
0110011 | 5 | |||
0110100 | 5 | |||
0110101 | 5 | |||
0110110 | 4 | |||
0110111 | 5 | |||
0111000 | 5 | |||
0111001 | 5 | |||
0111010 | 5 | |||
0111011 | 5 | |||
0111100 | 5 | |||
0111101 | 5 | |||
0111110 | 4 | |||
0111111 | 3 |
String | Complexity | Witness |
---|---|---|
00000000 | 2 | \(0^*\) |
00000001 | 3 | \(0^* 1\) |
00000010 | 4 | \(0^* 10\) |
00000011 | 4 | \(0^* 11\) |
00000100 | 5 | \(0^* 100\) |
00000101 | 5 | \(0^* 101\) |
00000110 | 5 | \(0^* 110\) |
00000111 | 5 | \(0^* 111\) |
00001000 | 6 | \(0^* 1000\) |
00001001 | 6 | \(0^* 1001\) |
00001010 | 6 | \(0^* 1010\) |
00001011 | 6 | \(0^* 1011\) |
00001100 | 6 | \(0^* 1100\) |
00001101 | 6 | \(0^* 1101\) |
00001110 | 6 | \(0^* 1110\) |
00001111 | 5 | d0: (1, 2, 3, 3, 0), d1: (4, 0, 1, 2, 0) better than \(0^* 1111\) |
00010000 | 6 | \(0001 0^*\) |
00010001 | \(\le\)5 | \((0001)^*\) |
00010010 | \(\le\)6 | \(0(001)^* 0\) |
00010011 | \(\le\)6 | \(0(001)^* 1\) |
00010100 | \(\le\)6 | \( 00 (01010…)00\) |
00010101 | \(\le\)5 | \( 00 (01)*\) |
00010110 | 5 | witness (K-H) |
00010111 | 5 | no trash |
00011000 | \(\le\)6 | \( 00011,00011,…\) |
00011001 | \(\le\)6 | \( 0 (0011,0011,…)\) |
00011010 | 6 | witness (K-H) |
00011011 | \(\le\)6 | \( 00(011)^*\) |
00011100 | 5 | witness (K-H) |
00011101 | 6 | witness (K-H) |
00011110 | \(\le 6\) (Christina M) (Jiehua H) | |
00011111 | \(\le 5\) (Jiehua H) | |
00100000 | \(\le 5\) (Christina M) (Jiehua H) | |
00100001 | \(\le 6\) (Christina M) (Jue W) | |
00100010 | \(\le 6\) (Jue W) | |
00100011 | \(\le 6\) (Jue W) | |
00100100 | \(\le 6\) (Jue W) | |
00100101 | \(\le 5\) (Jue W) | |
00100110 | \(\le 6\) (Jue W) | |
00100111 | \(\le 6\) (Jue W) | |
00101000 | \(\le 6\): \(a \rightarrow_0 b \rightarrow_0 c \rightarrow_1 b\) and \(c \rightarrow_0 d \rightarrow_0 e\) plus one thrash (Frank S) | |
00101001 | \(\le 6\) (Jue W) | |
00101010 | \(4\) (Christina M) | |
00101011 | 5\(\le 7\) | d0: (1, 2, 1, 0, 4), d1: (3, 0, 4, 0, 2) |
00101100 | \(\le 7\) | |
00101101 | \(\le 7\) | |
00101110 | \(\le 7\) | |
00101111 | \(\le 6\) (Christina M) | |
00110000 | \(\le 6\) (Christina M) (Jue W) | |
00110001 | \(\le 6\) (Jue W) | |
00110010 | \(\le 7\) | |
00110011 | \(\le 7\) | |
00110100 | \(\le 7\) | |
00110101 | \(\le 7\) | |
00110110 | \(\le 7\) | |
00110111 | \(\le 7\) | |
00111000 | \(\le 6\) (Jue W) | |
00111001 | \(\le 7\) | |
00111010 | \(\le 6\) (Jue W) | |
00111011 | \(\le 7\) | |
00111100 | \(\le 6\) (Christina M) (Jue W) | |
00111101 | \(\le 6\) (Christina M) (Jue W) | |
00111110 | \(\le 5\) (Christina M) (Jue W) | |
00111111 | \(4\) (Christina M) (Jue W) | |
01000000 | \(4\) (Christina M) (Jue W) | |
01000001 | \(\le 5\) (Christina M) (Jue W) | |
01000010 | \(\le 6\) (Christina M) (Jue W) | |
01000011 | \(\le 6\) (Christina M) (Jue W) | |
01000100 | \(\le 7\) | |
01000101 | \(\le 7\) | |
01000110 | \(\le 7\) | |
01000111 | \(\le 7\) | |
01001000 | \(\le 7\) | |
01001001 | \(\le 7\) | |
01001010 | \(\le 7\) | |
01001011 | \(\le 7\) | |
01001100 | \(\le 7\) | |
01001101 | \(\le 7\) | |
01001110 | \(\le 7\) | |
01001111 | \(\le 6\) (Christina M) | |
01010000 | \(\le 6\) (Christina M) | |
01010001 | \(\le 6\) (Christina M) | |
01010010 | \(\le 6\) (Christina M) | |
01010011 | \(\le 6\) (Christina M) | |
01010100 | 4 \(\le 4\) (Christina M) | |
01010101 | 3 (\(\le 4\) Christina M) | |
01010110 | \(\le 6\) (Christina M) | |
01010111 | \(\le 6\) (Christina M) | |
01011000 | \(\le 7\) | |
01011001 | \(\le 7\) | |
01011010 | \(\le 7\) | |
01011011 | \(\le 7\) | |
01011100 | \(\le 7\) | |
01011101 | \(\le 7\) | |
01011110 | \(\le 6\) (Christina M) | |
01011111 | \(5\) (Christina M) | |
01100000 | \(5\) (Christina M) | |
01100001 | \(\le 6\) (Christina M) | |
01100010 | \(\le 7\) | |
01100011 | \(\le 7\) | |
01100100 | \(\le 7\) | |
01100101 | \(\le 7\) | |
01100110 | \(\le 7\) | |
01100111 | \(\le 7\) | |
01101000 | \(\le 7\) | |
01101001 | \(\le 7\) | |
01101010 | \(\le 7\) | |
01101011 | \(\le 7\) | |
01101100 | \(\le 7\) | |
01101101 | \(\le 7\) | |
01101110 | \(\le 7\) | |
01101111 | \(\le 6\) | 4 consecutive |
01110000 | \(\le 6\) (Christina M) | |
01110001 | \(\le 7\) | |
01110010 | \(\le 7\) | |
01110011 | \(\le 7\) | |
01110100 | \(\le 7\) | |
01110101 | \(\le 7\) | |
01110110 | \(\le 7\) | |
01110111 | \(5\) (Jue W) | |
01111000 | \(\le 6\) (Christina M) | |
01111001 | \(\le 6\) | 4 consecutive |
01111010 | \(\le 6\) (Christina M) | |
01111011 | \(\le 6\) (Chelsea T) (Christina M) | |
01111100 | \(5\) (Chelsea T) (Christina M) | |
01111101 | \(5\) (Chelsea T) (Christina M) | |
01111110 | \(4\) (Chelsea T) (Christina M) | |
01111111 | \(3\) (Chelsea T) (Christina M) |