THE INTERSECTION PROBLEM FOR ALPHABETIC VECTOR MONOIDS



: HARJU T, KEESMAAT NW, KLEIJN HCM

Publisher: DUNOD

: 1994

: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

: RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS

: RAIRO-INF THEOR APPL

: 28

: 3-4

: 295

: 301

: 7

: 0988-3754

DOI: https://doi.org/10.1051/ita/1994283-402951


Let SIGMA, and GAMMA be two vector alphabets consisting of alphabetic vectors (a1, a2), where a1, a2 is-an-element-of A or {epsilon} for an alphabet A. We show that it is decidable whether or not SIGMA(x) and GAMMA(x) is the trivial submonoid of the direct product A* x A* for the generated submonoids SIGMA(x) and GAMMA(x). On the other hand we show that a simple version, obtained from letter-to-letter homomorphisms, of the modified Post Correspondence Problem is undecidable for alphabetic vectors.



Last updated on 2025-13-10 at 11:41