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},
     mrnumber = {1707965},
     zbl = {0946.68076},
     language = {en},
     url = {http://archive.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
SP  - 117
EP  - 124
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1999__33_2_117_0/
LA  - en
ID  - ITA_1999__33_2_117_0
ER  - 
%0 Journal Article
%A Halava, Vesa
%A Harju, Tero
%T Undecidability of the equivalence of finite substitutions on regular language
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 117-124
%V 33
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1999__33_2_117_0/
%G en
%F 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) no. 2, pp. 117-124. http://archive.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 | Zbl

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

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

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

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