An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
Dipartimento di Matematica e
Applicazioni, Università di Palermo, via Archirafi 34, 90123
Palermo, Italy; lgiambr;email@example.com
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