# An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid

Laura Giambruno; Antonio Restivo

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 3, page 503-524
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGiambruno, Laura, and Restivo, Antonio. "An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 503-524. <http://eudml.org/doc/250329>.

@article{Giambruno2008,

abstract = {
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 $\widetilde\{rk\}(H \cap K) \leq
\widetilde\{rk\}(H) \widetilde\{rk\}(K)$ where
$\widetilde\{rk\}(L)=\max(0,rk(L)-1)$ for any submonoid L.
},

author = {Giambruno, Laura, Restivo, Antonio},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Automata; free monoids; rank; intersection of submonoids; product automata},

language = {eng},

month = {6},

number = {3},

pages = {503-524},

publisher = {EDP Sciences},

title = {An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid},

url = {http://eudml.org/doc/250329},

volume = {42},

year = {2008},

}

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

DA - 2008/6//

PB - EDP Sciences

VL - 42

IS - 3

SP - 503

EP - 524

AB -
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 $\widetilde{rk}(H \cap K) \leq
\widetilde{rk}(H) \widetilde{rk}(K)$ where
$\widetilde{rk}(L)=\max(0,rk(L)-1)$ for any submonoid L.

LA - eng

KW - Automata; free monoids; rank; intersection of submonoids; product automata

UR - http://eudml.org/doc/250329

ER -

## References

top- J. Berstel and D. Perrin. Theory of Codes. Academic Press (1985). Zbl0587.68066
- V. Bruyére, D. Derencourt, M. Latteux. The meet operation in the lattice of codes. Theoretical Computer Science191 (1998) 117–129. Zbl1013.94009
- J. Clement, J. Duval, G.Guaiana, D. Perrin, G. Rindone. Paarsing with a finite dictionary. Theoretical Computer Science340 (2005) 432–442. Zbl1102.68058
- H.Cormen, E. Leiserson, L. Rivest. Introduction to Algorithms. The MIT Press (1990). Zbl1158.68538
- J.E. Hopcroft, J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Weisley Publishing Company (1979). Zbl0426.68001
- A.G. Howson. On the intersection of finitely generated free groups. J. London Math. Soc.29 (1954) 428–434. Zbl0056.02106
- J. Karhumäki. A note on intersection of free submonoids of a free monoid. Semigroup Forum29 (1984) 183–205. Zbl0555.20037
- M. Latteux and J. Leguy. On the composition of morphism and inverse morphisms. Lecture Notes in Computer Science154 (1983) 420–432. Zbl0523.68067
- J. Meakin and P. Weil. Sugroups of free groups: a contribution to the Hanna Neumann conjecture. Geometriae Dedicata94 (2002) 33–43. Zbl1032.20017
- H. Neumann. On intersections of finitely generated subgroups of free groups. Publ. Math. Debrecen4 (1956) 186–189. Zbl0070.02001
- W.D. Neumann. On intersections of finitely generated subgroups of free groups. Lect. Notes Math.1456 (1990) 161–170.
- B. Tilson. The intersection of free submonoids of a free monoid is free. Semigroup Forum4 (1972) 345–350. Zbl0261.20060

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.