The simplest language where equivalence of finite substitutions is undecidable
| Authors | |
|---|---|
| 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 | |
| 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: |