UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
Giovanni Pighizzini, Jeffrey O. Shallit · International Journal of Foundations of Computer Science · 2002
In this paper we give the cost, in terms of states, of some basic operations (union, intersection, concatenation, and Kleene star) on regular languages in the unary case (where the alphabet contains only one symbol). These costs are given by explicitly determining the number of states in the noncyclic and cyclic parts of the resulting automata. Furthermore, we prove that our bounds are optimal. We also present an interesting connection to Jacobsthal's function from number theory.