![Jak na přijímačky](https://cdn.muni.cz/media/3633702/image_1.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
Identity checking problem for transformation monoids
Název česky | Problém kontroly identit v transformačních monoidech |
---|---|
Autoři | |
Rok publikování | 2012 |
Druh | Článek v odborném periodiku |
Časopis / Zdroj | Semigroup Forum |
Fakulta / Pracoviště MU | |
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: |