The Equivalence Problem of Finite Substitutions on abc, with Applications

We show that it is undecidable whether or not two finite substitutions are equivalent on the fixed regular language ab*c. This gives an unexpected answer to a question proposed in 1985 by Culik II and Karhumäki. At the same time it can be seen as the final result in a series of undecidability result...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2003-08, Vol.14 (4), p.699-710
Main Authors: Karhumäki, J., Lisovik, L. P.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that it is undecidable whether or not two finite substitutions are equivalent on the fixed regular language ab*c. This gives an unexpected answer to a question proposed in 1985 by Culik II and Karhumäki. At the same time it can be seen as the final result in a series of undecidability results for finite transducers initiated in 1968 by Griffiths. An application to systems of equations over finite languages is given.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054103001960