Complexity issues of checking identities in finite monoids

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