The power of commuting with finite sets of words

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Síla komutování s konečnými množinami slov
Autoři

KUNC Michal

Rok publikování 2005
Druh Článek ve sborníku
Konference STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www http://www.springerlink.com/link.asp?id=72ul1qvmpr3utqyp
Obor Obecná matematika
Klíčová slova Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine
Popis V práci ukazujeme, že lze zkonstruovat konečný jazyk L takový, že největší jazyk komutující s L není rekurzívně vyčíslitelný. Tímto dáváme negativní odpověď na otázku, kterou položil Conway v roce 1971, a rovněž silně vyvracíme jeho hypotézu, že maximální řešení systémů pololineárních nerovnic jsou bezkontextová.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.