Complexity issues of checking identities in finite monoids

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	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ů