6533b7d3fe1ef96bd1260a6b

RESEARCH PRODUCT

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

subject

description

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 Karhumaki on the cha- racterization 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 �(H ∩ K) ≤ �(H)�(K )w here�(L )=m ax(0,rk(L) − 1) for any submonoid L. Mathematics Subject Classification. 68Q70, 68Q45, 20M35.