Complexity issues of checking identities in finite monoids

Logo poskytovatele

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.