| KUNC, Michal. The power of commuting with finite sets of words. In STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings. Berlin: Springer-Verlag, 2005, p. 569-580. ISBN 3-540-24998-2. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{568467,
author = {Kunc, Michal},
address = {Berlin},
booktitle = {STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings},
keywords = {Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine},
language = {eng},
location = {Berlin},
isbn = {3-540-24998-2},
pages = {569-580},
publisher = {Springer-Verlag},
title = {The power of commuting with finite sets of words},
url = {http://www.springerlink.com/link.asp?id=72ul1qvmpr3utqyp},
year = {2005}
}
TY - JOUR
ID - 568467
AU - Kunc, Michal
PY - 2005
TI - The power of commuting with finite sets of words
PB - Springer-Verlag
CY - Berlin
SN - 3540249982
KW - Commutation of languages
KW - Language equation
KW - Regular language
KW - Recursively enumerable language
KW - Minsky machine
UR - http://www.springerlink.com/link.asp?id=72ul1qvmpr3utqyp
N2 - We show that one can construct a finite language L such that the largest language commuting with L is not recursively enumerable. This gives a negative answer to the question raised by Conway in 1971 and also strongly disproves Conway's conjecture on context-freeness of maximal solutions of systems of semi-linear inequalities.
ER -
KUNC, Michal. The power of commuting with finite sets of words. In \textit{STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings}. Berlin: Springer-Verlag, 2005, p.~569-580. ISBN~3-540-24998-2.
|
