Publication details

The simplest language where equivalence of finite substitutions is undecidable

Investor logo
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.

More info