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 and 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 .
Mots-clés : automata, free monoids, rank, intersection of submonoids
@article{ITA_2008__42_3_503_0, author = {Giambruno, Laura and Restivo, Antonio}, title = {An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {503--524}, publisher = {EDP-Sciences}, volume = {42}, number = {3}, year = {2008}, doi = {10.1051/ita:2008014}, mrnumber = {2434032}, zbl = {1149.68058}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2008014/} }
TY - JOUR AU - Giambruno, Laura AU - Restivo, Antonio TI - An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2008 SP - 503 EP - 524 VL - 42 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2008014/ DO - 10.1051/ita:2008014 LA - en ID - ITA_2008__42_3_503_0 ER -
%0 Journal Article %A Giambruno, Laura %A Restivo, Antonio %T An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 503-524 %V 42 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2008014/ %R 10.1051/ita:2008014 %G en %F ITA_2008__42_3_503_0
Giambruno, Laura; Restivo, Antonio. An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 503-524. doi : 10.1051/ita:2008014. http://archive.numdam.org/articles/10.1051/ita:2008014/
[1] Theory of Codes. Academic Press (1985). | MR | Zbl
and .[2] The meet operation in the lattice of codes. Theoretical Computer Science 191 (1998) 117-129. | MR | Zbl
, , .[3] Paarsing with a finite dictionary. Theoretical Computer Science 340 (2005) 432-442. | MR | Zbl
, , , , .[4] Introduction to Algorithms. The MIT Press (1990). | MR | Zbl
, , .[5] Introduction to Automata Theory, Languages and Computation. Addison-Weisley Publishing Company (1979). | MR | Zbl
, .[6] On the intersection of finitely generated free groups. J. London Math. Soc. 29 (1954) 428-434. | MR | Zbl
.[7] A note on intersection of free submonoids of a free monoid. Semigroup Forum 29 (1984) 183-205. | MR | Zbl
.[8] On the composition of morphism and inverse morphisms. Lecture Notes in Computer Science 154 (1983) 420-432. | MR | Zbl
and .[9] Sugroups of free groups: a contribution to the Hanna Neumann conjecture. Geometriae Dedicata 94 (2002) 33-43. | MR | Zbl
and .[10] On intersections of finitely generated subgroups of free groups. Publ. Math. Debrecen 4 (1956) 186-189. | MR | Zbl
.[11] On intersections of finitely generated subgroups of free groups. Lect. Notes Math. 1456 (1990) 161-170. | MR | Zbl
.[12] The intersection of free submonoids of a free monoid is free. Semigroup Forum 4 (1972) 345-350. | MR | Zbl
.Cité par Sources :