Undecidability of the equivalence of finite substitutions on regular language
Halava, Vesa ; Harju, Tero
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 117-124 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{ITA_1999__33_2_117_0,
     author = {Halava, Vesa and Harju, Tero},
     title = {Undecidability of the equivalence of finite substitutions on regular language},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {117-124},
     mrnumber = {1707965},
     zbl = {0946.68076},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_2_117_0}
}

Halava, Vesa; Harju, Tero. Undecidability of the equivalence of finite substitutions on regular language. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 117-124. http://gdmltest.u-ga.fr/item/ITA_1999__33_2_117_0/

[1] V. Halava and T. Harju, Undecidability in integer weighted finite automata. Fund. Inform., to appear. | MR 1718120 | Zbl 0935.68060

[2] J. Karhumäki, Equations over finite sets of words and equivalence problems in automata theory. Theoret. Comput. Sci. 108 (1993) 103-118. | MR 1203824 | Zbl 0787.20035

[3] L. P. Lisovik, An undecidable problem for countable Markov chains. Cybernetics 27 (1991) 163-169. | MR 1123181 | Zbl 0800.68581

[4] L. P. Lisovik, Nondeterministic systems and finite substitutions on regular language. Bull. European Assoc. Theoret. Comput. Sci. (1997) 156-160. | MR 1621600 | Zbl 0886.68089

[5] P. Turakainen, The undecidability of some equivalence problems concerning ngsm's and finite substitutions. Theoret. Comput. Sci. 174 (1997) 269-274. | MR 1439242 | Zbl 0908.68098