The simplest language where equivalence of finite substitutions is undecidable

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KUNC Michal

Year of publication 2007
Type Article in Proceedings
Conference Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings
MU Faculty or unit

Faculty of Science

Citation
Web http://dx.doi.org/10.1007/978-3-540-74240-1_32
Field General mathematics
Keywords Finite substitution; Language equation; Finite transducer; Regular language; Equivalence problem
Description We show that it is undecidable whether two finite substitutions agree on the binary language a*b. This in particular means that equivalence of nondeterministic finite transducers is undecidable even for two-state transducers with unary input alphabet and whose all transitions start from the initial state.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.