A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
THE INTERSECTION PROBLEM FOR ALPHABETIC VECTOR MONOIDS
Tekijät: HARJU T, KEESMAAT NW, KLEIJN HCM
Kustantaja: DUNOD
Julkaisuvuosi: 1994
Lehti:: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
Lehden akronyymi: RAIRO-INF THEOR APPL
Vuosikerta: 28
Numero: 3-4
Aloitussivu: 295
Lopetussivu: 301
Sivujen määrä: 7
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita/1994283-402951
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali