# 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 (2011).

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)