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

Abstract

top
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 r k ˜ ( H ∩ K ) ≤ r k ˜ ( H ) r k ˜ ( K ) where r k ˜ ( L ) = max ( 0 , r k ( L ) - 1 ) for any submonoid L.

How to cite

top

Giambruno, 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
  1. J. Berstel and D. Perrin. Theory of Codes. Academic Press (1985).  
  2. V. Bruyére, D. Derencourt, M. Latteux. The meet operation in the lattice of codes. Theoretical Computer Science191 (1998) 117–129.  
  3. J. Clement, J. Duval, G.Guaiana, D. Perrin, G. Rindone. Paarsing with a finite dictionary. Theoretical Computer Science340 (2005) 432–442.  
  4. H.Cormen, E. Leiserson, L. Rivest. Introduction to Algorithms. The MIT Press (1990).  
  5. J.E. Hopcroft, J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Weisley Publishing Company (1979).  
  6. A.G. Howson. On the intersection of finitely generated free groups. J. London Math. Soc.29 (1954) 428–434.  
  7. J. Karhumäki. A note on intersection of free submonoids of a free monoid. Semigroup Forum29 (1984) 183–205.  
  8. M. Latteux and J. Leguy. On the composition of morphism and inverse morphisms. Lecture Notes in Computer Science154 (1983) 420–432.  
  9. J. Meakin and P. Weil. Sugroups of free groups: a contribution to the Hanna Neumann conjecture. Geometriae Dedicata94 (2002) 33–43.  
  10. H. Neumann. On intersections of finitely generated subgroups of free groups. Publ. Math. Debrecen4 (1956) 186–189.  
  11. W.D. Neumann. On intersections of finitely generated subgroups of free groups. Lect. Notes Math.1456 (1990) 161–170.  
  12. B. Tilson. The intersection of free submonoids of a free monoid is free. Semigroup Forum4 (1972) 345–350.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.