Informace o publikaci

Identity checking problem for transformation monoids

Logo poskytovatele
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
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:

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

Další info