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.

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

DOI : https://doi.org/10.1051/ita:2008014
Classification : 68Q70,  68Q45,  20M35
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},
     zbl = {1149.68058},
     mrnumber = {2434032},
     language = {en},
     url = {http://www.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
DA  - 2008///
SP  - 503
EP  - 524
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2008014/
UR  - https://zbmath.org/?q=an%3A1149.68058
UR  - https://www.ams.org/mathscinet-getitem?mr=2434032
UR  - https://doi.org/10.1051/ita:2008014
DO  - 10.1051/ita:2008014
LA  - en
ID  - ITA_2008__42_3_503_0
ER  - 
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://www.numdam.org/articles/10.1051/ita:2008014/

[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

Cité par Sources :