| 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, p. 365-375. ISBN 978-3-540-74239-5. |
Other formats:
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, p.~365-375. ISBN~978-3-540-74239-5.
|
