Document RAIRO-Theor. Inf. Appl. 42, 503-524 (2008)
DOI: 10.1051/ita:2008014
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
Laura Giambruno and Antonio RestivoDipartimento di Matematica e Applicazioni, Università di Palermo, via Archirafi 34, 90123 Palermo, Italy; lgiambr;restivo@math.unipa.it
Published online: 3 June 2008
Abstract
We investigate the intersection of two finitely generated submonoids
of the free monoid on a finite alphabet. To this purpose, we
consider automata that recognize such submonoids and we study the
product automata recognizing their intersection. By using automata
methods we obtain a new proof of a result of Karhumäki on the
characterization of the intersection of two submonoids of
rank two, in the case of prefix (or suffix) generators. In a more
general setting, for an arbitrary number of generators, we prove
that if H and K are two finitely generated submonoids generated
by prefix sets such that the product automaton associated to 
has a given special property then
where
for any submonoid L.
Mathematics Subject Classification. 68Q70, 68Q45, 20M35
Key words: Automata -- free monoids -- rank -- intersection of submonoids
© EDP Sciences 2008