Deterministic automaton complexity of strings

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).\]


String 011100
Automaton witnessing the complexity of the string 011100. (For simplicity, the trash state where any missing arrow goes is not shown.)

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)