The power of commuting with finite sets of words

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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