Complexity issues of checking identities in finite monoids

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	Složitost kontroly identit v konečných monoidech
Autoři	KLÍMA Ondřej
Rok publikování	2009
Druh	Článek v odborném periodiku
Časopis / Zdroj	Semigroup Forum
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
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. Nalezli jsme nejmenší monoid pro který je tento problém coNPúplný a popsali zásadní třídu konečných monoidů pro které je problém efektivně řešitelný.
Související projekty:	Institut Teoretické Informatiky Matematické struktury a jejich fyzikální aplikace Algebraické metody v teorii automatů a formálních jazyků