A1 Refereed original research article in a scientific journal
THE INTERSECTION PROBLEM FOR ALPHABETIC VECTOR MONOIDS
Authors: HARJU T, KEESMAAT NW, KLEIJN HCM
Publisher: DUNOD
Publication year: 1994
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
Journal acronym: RAIRO-INF THEOR APPL
Volume: 28
Issue: 3-4
First page : 295
Last page: 301
Number of pages: 7
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita/1994283-402951
Abstract
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.
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.
UTU Research Portal