Undecidability of the equivalence of finite substitutions on regular language
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 33, Issue: 2, page 117-124
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topHalava, Vesa, and Harju, Tero. "Undecidability of the equivalence of finite substitutions on regular language." RAIRO - Theoretical Informatics and Applications 33.2 (2010): 117-124. <http://eudml.org/doc/222067>.
@article{Halava2010,
abstract = {
A simplified proof is given for the following result due to
Lisovik: it is undecidable for two given ε–free finite
substitutions, whether they are equivalent on the regular language
b\{0,1\}*c.
},
author = {Halava, Vesa, Harju, Tero},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {regular language},
language = {eng},
month = {3},
number = {2},
pages = {117-124},
publisher = {EDP Sciences},
title = {Undecidability of the equivalence of finite substitutions on regular language},
url = {http://eudml.org/doc/222067},
volume = {33},
year = {2010},
}
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
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 2
SP - 117
EP - 124
AB -
A simplified proof is given for the following result due to
Lisovik: it is undecidable for two given ε–free finite
substitutions, whether they are equivalent on the regular language
b{0,1}*c.
LA - eng
KW - regular language
UR - http://eudml.org/doc/222067
ER -
References
top- V. Halava and T. Harju, Undecidability in integer weighted finite automata. Fund. Inform., to appear.
- J. Karhumäki, Equations over finite sets of words and equivalence problems in automata theory. Theoret. Comput. Sci.108 (1993) 103-118.
- L.P. Lisovik, An undecidable problem for countable Markov chains. Cybernetics27 (1991) 163-169.
- L.P. Lisovik, Nondeterministic systems and finite substitutions on regular language. Bull. European Assoc. Theoret. Comput. Sci. (1997) 156-160.
- P. Turakainen, The undecidability of some equivalence problems concerning ngsm's and finite substitutions. Theoret. Comput. Sci.174 (1997) 269-274.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.