Kolmogorov defined the complexity of a string x, $C(x)$ , as roughly the size of the smallest program (formally, a Turing machine or a program in some well-defined model) that prints that string. We give examples that all use a two-letter alphabet.

Let $x\in \{0,1\}^n$ . Then $C(x)\le n+O(1)$ because the following program has length ${n+O(1)}$ and prints x: print(x). Let $x=0^n$ . Then $C(x)\le \log _2 n+O(1)$ because the following program has length $\log _2 n+O(1)$ and prints x: For i=1 to n print(0). Here n is written in binary. The complexity might be lower. For example, if $n=2^m$ , then $C(x)\le \log _2\log _2 n+O(1)$ . Let x be formed by flipping a coin n times and recording the outcomes. From the first example, $C(x)\le n+O(1)$ . With very high probability, $C(x)\ge n+\Omega (1)$ .

What if, instead of using programs, one used finite automata? Finite automata are recognizers, not generators, so instead of requiring the device to output x, we will require the device to accept x. That cannot be right, since otherwise we could simply use a device that accepts every string. We will next give several definitions of the complexity of a string using finite automata that deal with these issues. That is the topic of this book; however, the book also goes in a few other directions, such as infinite strings. The book has many definitions. We give some of them here.

A DFA is a deterministic finite automaton. An incomplete DFA is a DFA except that the transition function $\delta \colon Q\times \Sigma \to Q$ mapping pairs of states and letters to states may be partial. Acceptance is defined by saying that an automaton accepts a string if it processes the string completely and at the end is in an accept state. An NFA is a nondeterministic finite automaton.

Let $\Sigma $ be a finite alphabet, and let $n\in \mathbb {N}$ . All of the definitions of complexity A (and variants) should really be written $A_\Sigma (x)$ , but we will just write $A(x)$ . All DFAs referenced are assumed to be $(Q,\Sigma ,\delta ,s,F)$ , where Q is the set of states, $\Sigma $ is the alphabet, $\delta $ is the transition function, s is the start state, and F is the set of final states. Let $x\in \Sigma ^n$ (so x is of length n).

$A(x)$ is the least number of states in the smallest DFA M such that (1) $M(x)$ accepts, and (2) for all $y\in \Sigma ^n-\{x\}$ , $M(y)$ rejects. $A^-(x)$ is the least number of states in the smallest partial DFA M such that (1) $M(x)$ accepts, and (2) for all $y\in \Sigma ^n-\{x\}$ , $M(y)$ rejects. $A^{\mathrm {perm}}(x)$ is the least number of states in the smallest DFA M such that (1) $M(x)$ accepts, (2) for all $y\in \Sigma ^n-\{x\}$ , $M(y)$ rejects, and (3) for all $\sigma \in \Sigma $ the function from Q to Q defined by $f(q)=\delta (q,\sigma )$ is a permutation. $A^{\mathrm {tra}}(x)$ is the least number of states in the smallest DFA M such that (1) $M(x)$ accepts, (2) for all $y\in \Sigma ^n-\{x\}$ , $M(y)$ rejects, and (3) for all $p,q\in Q$ there exists a $\sigma \in \Sigma $ such that $\delta (p,\sigma )=q$ . $A_N(x)$ is the least number of states in the smallest NFA M such that (1) $M(x)$ accepts, (2) for all $y\in \Sigma ^n-\{x\}$ , $M(y)$ rejects, and (3) there is only one accepting path for x. The book also uses $A_{Nu}$ for this notion to distinguish it from other definitions (see below) of complexity using an NFA. The u stands for unique. $A_{Ne}(x)$ is the least number of states in the smallest NFA M such that (1) $M(x)$ accepts, and (2) for all $y\in \Sigma ^n-\{x\}$ , $M(y)$ rejects. The e stands for exact. $A_{Nc}(x)$ is the least number of states in the smallest NFA M such that (1) $M(x)$ accepts, (2) for all $y\in \Sigma ^n-\{x\}$ , $M(y)$ rejects, (3) there is only one accepting path for x, and (4) the one accepting path visits every edge. The c stands for covering.

The book also has some definitions based on the number of edges in a DFA, partial DFA, NFA, and variants. There are many more definitions as well. Page 77 contains a chart of around 25 different definitions and how they relate.

There are several types of theorems in this book.

First, upper or lower bounds on the complexity of parameterized sets of strings are established. Examples include the following.

Theorem 1.74. If $a_1,\ldots ,a_k$ are k different symbols, then

$$\begin{align*}A(a_1^n\cdots a_k^n)=O(n^{1-1/k}), \end{align*}$$

where the constant in the big-O depends on k. The proof of Theorem 1.74 uses lemmas about solving Diophantine equations.

The book covers several other concepts. If $x\in \{0,1\}^n$ , then ${A_N(x)\le b(n)=\lfloor n/2\rfloor +1}$ . The deficiency of x is $b(n)-A_N(x)$ . This concept is studied extensively. In the usual Kolmogorov complexity, $C(x\mid y)$ is the shortest TM that will, when run with y on the tape, output x. This book considers an analogous notion for automatic complexity.

The book also covers infinite strings. A sample set of theorems is as follows. A string x is square-free if there is no $w\ne \epsilon $ such that $ww$ is a substring of x. If $|\Sigma |\in \{1,2\}$ , then there are no infinite square-free strings. If $|\Sigma |=3$ , then there is an infinite square-free string.

Some of the problems that arise from studying automatic complexity are NP-complete. The above account is not complete. The concept of modifying Kolmogorov complexity with finite automata instead of TMs is interesting. Some of the theorems have clever proofs, bring up other branches of mathematics, or both.

The book gave many different notions of complexity. I stated eight of them above. This is a problem with the book: there are too many definitions. Some of them are rather obscure, and not much is proved about them. The book would have been better with fewer definitions and more development of the central ones.

Nonetheless, the book is a good supplement to a course that covers automata theory or Kolmogorov complexity.