The Equivalence Problem of Finite Substitutions on ab*c , with Applications
Juhani Karhumäki, Leonid P. Lisovik · International Journal of Foundations of Computer Science · 2003
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.