The simplest language where equivalence of finite substitutions is undecidable

Warning

This publication doesn't include Institute of Computer Science. 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:	Mathematical structures and their physical applications Algebraic Methods in Automata and Formal Language Theory