Undecidability of the equivalence of finite substitutions on regular language



: Halava V, Harju T

Publisher: GAUTHIER-VILLARS/EDITIONS ELSEVIER

: 1999

: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

: RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS

: RAIRO-INF THEOR APPL

: 33

: 2

: 117

: 124

: 8

: 0988-3754

DOI: https://doi.org/10.1051/ita:1999109


A simplified proof is given for the following result due to Lisovik: it is undecidable for two given epsilon-free finite substitutions, whether they are equivalent on the regular language b{0, 1}*c.



Last updated on 2025-13-10 at 13:43