Identity checking problem for transformation monoids

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

• Institut Teoretické Informatiky
• Matematické struktury a jejich fyzikální aplikace
• Algebraické metody v teorii automatů a formálních jazyků II