Automatic complexity of strings

The 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\). 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 3,\] \[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).\]

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

This exact notion of complexity has been studied before (thanks to Mia Minnes for the reference) by Shallit and Wang in 2001.

• Statistical Inference
• Transition to Advanced Mathematics
• A strong law of computationally weak subsets

• automata
• Brownian motion
• NSF DMS-0901020
• publications
• randomness
• research
• teaching
• Uncategorized
• undergraduate research
• web pages