An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
Giambruno, Laura ; Restivo, Antonio
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 503-524 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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 H∩K has a given special property then rk ˜(H∩K)≤rk ˜(H)rk ˜(K) where rk ˜(L)=max(0,rk(L)-1) for any submonoid L.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2008014
Classification:  68Q70,  68Q45,  20M35 
@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},
     volume = {42},
     year = {2008},
     pages = {503-524},
     doi = {10.1051/ita:2008014},
     mrnumber = {2434032},
     zbl = {1149.68058},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 503-524. doi : 10.1051/ita:2008014. http://gdmltest.u-ga.fr/item/ITA_2008__42_3_503_0/

[1] J. Berstel and D. Perrin. Theory of Codes. Academic Press (1985). | MR 797069 | Zbl 0587.68066

[2] V. Bruyére, D. Derencourt, M. Latteux. The meet operation in the lattice of codes. Theoretical Computer Science 191 (1998) 117-129. | MR 1490566 | Zbl 1013.94009

[3] J. Clement, J. Duval, G. Guaiana, D. Perrin, G. Rindone. Paarsing with a finite dictionary. Theoretical Computer Science 340 (2005) 432-442. | MR 2150764 | Zbl 1102.68058

[4] H. Cormen, E. Leiserson, L. Rivest. Introduction to Algorithms. The MIT Press (1990). | MR 1066870 | Zbl 1158.68538

[5] J.E. Hopcroft, J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Weisley Publishing Company (1979). | MR 645539 | Zbl 0426.68001

[6] A.G. Howson. On the intersection of finitely generated free groups. J. London Math. Soc. 29 (1954) 428-434. | MR 65557 | Zbl 0056.02106

[7] J. Karhumäki. A note on intersection of free submonoids of a free monoid. Semigroup Forum 29 (1984) 183-205. | MR 742132 | Zbl 0555.20037

[8] M. Latteux and J. Leguy. On the composition of morphism and inverse morphisms. Lecture Notes in Computer Science 154 (1983) 420-432. | MR 727673 | Zbl 0523.68067

[9] J. Meakin and P. Weil. Sugroups of free groups: a contribution to the Hanna Neumann conjecture. Geometriae Dedicata 94 (2002) 33-43. | MR 1950872 | Zbl 1032.20017

[10] H. Neumann. On intersections of finitely generated subgroups of free groups. Publ. Math. Debrecen 4 (1956) 186-189. | MR 78992 | Zbl 0070.02001

[11] W.D. Neumann. On intersections of finitely generated subgroups of free groups. Lect. Notes Math. 1456 (1990) 161-170. | MR 1092229 | Zbl 0722.20016

[12] B. Tilson. The intersection of free submonoids of a free monoid is free. Semigroup Forum 4 (1972) 345-350. | MR 311807 | Zbl 0261.20060