Undecidability of the equivalence of finite substitutions on regular language
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 2, pp. 117-124.
@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},
     pages = {117--124},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {2},
     year = {1999},
     zbl = {0946.68076},
     mrnumber = {1707965},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1999__33_2_117_0/}
}
TY  - JOUR
AU  - Halava, Vesa
AU  - Harju, Tero
TI  - Undecidability of the equivalence of finite substitutions on regular language
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1999
DA  - 1999///
SP  - 117
EP  - 124
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1999__33_2_117_0/
UR  - https://zbmath.org/?q=an%3A0946.68076
UR  - https://www.ams.org/mathscinet-getitem?mr=1707965
LA  - en
ID  - ITA_1999__33_2_117_0
ER  - 
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) no. 2, pp. 117-124. http://www.numdam.org/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