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, Volume 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\cap K$ has a given special property then $\stackrel{˜}{rk}\left(H\cap K\right)\le \stackrel{˜}{rk}\left(H\right)\stackrel{˜}{rk}\left(K\right)$ where $\stackrel{˜}{rk}\left(L\right)=max\left(0,rk\left(L\right)-1\right)$ for any submonoid $L$.

DOI: 10.1051/ita:2008014
Classification: 68Q70,  68Q45,  20M35
Keywords: 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  - 
%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 https://doi.org/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, Volume 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

Cited by Sources: