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:	Matematické struktury algebry a geometrie