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 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.

DOI : 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},
     mrnumber = {2434032},
     zbl = {1149.68058},
     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
SP  - 503
EP  - 524
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.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://www.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://www.numdam.org/articles/10.1051/ita:2008014/

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :