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
Abstract
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.
Download
Compressed postscript
Compressed dvi