Identity checking problem for transformation monoids

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.

Název česky	Problém kontroly identit v transformačních monoidech
Autoři	KLÍMA Ondřej
Rok publikování	2012
Druh	Článek v odborném periodiku
Časopis / Zdroj	Semigroup Forum
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace	KLÍMA, Ondřej. Identity checking problem for transformation monoids. Semigroup Forum. Springer-Verlag, 2012, roč. 84, č. 3, s. 487-498. ISSN 0037-1912. Dostupné z: https://dx.doi.org/10.1007/s00233-012-9401-7.
Doi	http://dx.doi.org/10.1007/s00233-012-9401-7
Obor	Obecná matematika
Klíčová slova	Checking identities; Finite semigroups; Complexity
Popis	Studujeme výpočetní složitost problému kontroly identit v pevně daném konečném monoidu. Dokázali jsem, že tento problém je coNP-těžký pro transformační monoid čtyřprvkové množiny. Tím jsme dokončili popis složitosti problému kontroly identit v transformačních monoidech.
Související projekty:	Institut Teoretické Informatiky Matematické struktury a jejich fyzikální aplikace Algebraické metody v teorii automatů a formálních jazyků II