Undecidability of the equivalence of finite substitutions on regular language

Vesa Halava; Tero Harju

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1999)

  • Volume: 33, Issue: 2, page 117-124
  • ISSN: 0988-3754

How to cite

top

Halava, Vesa, and Harju, Tero. "Undecidability of the equivalence of finite substitutions on regular language." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 33.2 (1999): 117-124. <http://eudml.org/doc/92594>.

@article{Halava1999,
author = {Halava, Vesa, Harju, Tero},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {regular language},
language = {eng},
number = {2},
pages = {117-124},
publisher = {EDP-Sciences},
title = {Undecidability of the equivalence of finite substitutions on regular language},
url = {http://eudml.org/doc/92594},
volume = {33},
year = {1999},
}

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
PB - EDP-Sciences
VL - 33
IS - 2
SP - 117
EP - 124
LA - eng
KW - regular language
UR - http://eudml.org/doc/92594
ER -

References

top
  1. [1] V. Halava and T. Harju, Undecidability in integer weighted finite automata. Fund. Inform., to appear. Zbl0935.68060MR1718120
  2. [2] J. Karhumäki, Equations over finite sets of words and equivalence problems in automata theory. Theoret. Comput. Sci. 108 (1993) 103-118. Zbl0787.20035MR1203824
  3. [3] L. P. Lisovik, An undecidable problem for countable Markov chains. Cybernetics 27 (1991) 163-169. Zbl0800.68581MR1123181
  4. [4] L. P. Lisovik, Nondeterministic systems and finite substitutions on regular language. Bull. European Assoc. Theoret. Comput. Sci. (1997) 156-160. Zbl0886.68089MR1621600
  5. [5] P. Turakainen, The undecidability of some equivalence problems concerning ngsm's and finite substitutions. Theoret. Comput. Sci. 174 (1997) 269-274. Zbl0908.68098MR1439242

NotesEmbed ?

top

You must be logged in to post comments.