A1 Refereed original research article in a scientific journal

Undecidability of the equivalence of finite substitutions on regular language



Authors: Halava V, Harju T

Publisher: GAUTHIER-VILLARS/EDITIONS ELSEVIER

Publication year: 1999

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

Journal name in source: RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS

Journal acronym: RAIRO-INF THEOR APPL

Volume: 33

Issue: 2

First page : 117

Last page: 124

Number of pages: 8

ISSN: 0988-3754

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


Abstract
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.


Research Areas



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