Other formats:
BibTeX
LaTeX
RIS
@article{720943,
author = {Kunc, Michal},
article_location = {New York},
article_number = {4},
keywords = {Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine},
language = {eng},
issn = {1432-4350},
journal = {Theory of Computing Systems},
title = {The power of commuting with finite sets of words},
url = {http://dx.doi.org/10.1007/s00224-006-1321-z},
volume = {40},
year = {2007}
}
TY - JOUR
ID - 720943
AU - Kunc, Michal
PY - 2007
TI - The power of commuting with finite sets of words
JF - Theory of Computing Systems
VL - 40
IS - 4
SP - 521
EP - 521
PB - Springer
SN - 14324350
KW - Commutation of languages
KW - Language equation
KW - Regular language
KW - Recursively enumerable language
KW - Minsky machine
UR - http://dx.doi.org/10.1007/s00224-006-1321-z
N2 - We 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. \textit{Theory of Computing Systems}. New York: Springer, 2007, vol.~40, No~4, p.~521-551. ISSN~1432-4350.
|
