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

Giambruno, Laura; Restivo, Antonio

doi:10.1051/ita:2008014

Giambruno, Laura ; Restivo, Antonio

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 503-524

Voir la notice de l'article provenant de la source Numdam

Résumé

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

MR Zbl

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},
     mrnumber = {2434032},
     zbl = {1149.68058},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :

Parcourir par

Geodesic

Parcourir par