The power of commuting with finite sets of words

Varování

Publikace nespadá pod Fakultu sportovních studií, 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í	2007
Druh	Článek v odborném periodiku
Časopis / Zdroj	Theory of Computing Systems
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
www	http://dx.doi.org/10.1007/s00224-006-1321-z
Obor	Obecná matematika
Klíčová slova	Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine
Popis	V práci konstruujeme 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 a jejich fyzikální aplikace