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, s. 569-580. ISBN 3-540-24998-2. |
Další formáty:
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, s.~569-580. ISBN~3-540-24998-2.
|