Unary language concatenation and its state complexity

Giovanni Pighizzini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
In this paper we study the costs, in terms of states, of some basic operations on regular languages, in the unary case, namely in the case of languages defined over a one letter alphabet. In particular, we concentrate our attention on the concatenation. The costs, which are proved to be tight, are given by explicitly indicating the number of states in the noncyclic and in the cyclic parts of the resulting automata.

Compressed postscript
Compressed dvi