KUNC, Michal. The simplest language where equivalence of finite substitutions is undecidable. In Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings. Berlin: Springer, 2007, s. 365-375. ISBN 978-3-540-74239-5. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{723254, author = {Kunc, Michal}, address = {Berlin}, booktitle = {Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings}, keywords = {Finite substitution; Language equation; Finite transducer; Regular language; Equivalence problem}, language = {eng}, location = {Berlin}, isbn = {978-3-540-74239-5}, pages = {365-375}, publisher = {Springer}, title = {The simplest language where equivalence of finite substitutions is undecidable}, url = {http://dx.doi.org/10.1007/978-3-540-74240-1_32}, year = {2007} }
TY - JOUR ID - 723254 AU - Kunc, Michal PY - 2007 TI - The simplest language where equivalence of finite substitutions is undecidable PB - Springer CY - Berlin SN - 9783540742395 KW - Finite substitution KW - Language equation KW - Finite transducer KW - Regular language KW - Equivalence problem UR - http://dx.doi.org/10.1007/978-3-540-74240-1_32 N2 - 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. ER -
KUNC, Michal. The simplest language where equivalence of finite substitutions is undecidable. In \textit{Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings}. Berlin: Springer, 2007, s.~365-375. ISBN~978-3-540-74239-5.
|