Taylor J. Smith

Arto Salomaa, Kai Salomaa, Taylor J. Smith

The state complexity, respectively, nondeterministic state complexity of a regular language $L$ is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for $L$. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.

Taylor J. Smith

The notion of a two-dimensional word arises naturally in the study of combinatorics on words, while the iterative construction of pedal triangles results in a rich dynamical system in the study of geometry. At first, these two classes of objects seem to be unrelated. However, it is known that for all $n \geq 1$, the number of primitive two-dimensional words of dimension $2 \times n$ over a binary alphabet agrees with the number of triangles whose first similar pedal triangle is their $n$th pedal triangle. We construct a finite four-symbol coding of the sorted pedal map and use the resulting branch itineraries to give a bijection between these two classes.