Complexity issues of checking identities in finite monoids

• Authors: KLÍMA Ondřej
• Year of publication: 2009
• Type: Article in Periodical
• Magazine / Source: Semigroup Forum
• MU Faculty or unit: Faculty of Science
• Field: General mathematics
• Keywords: Checking identities Finite semigroups Complexity
• Description: We study the computational complexity of checking identities in a fixed finite monoid. We find the smallest monoid for which this problem is coNPcomplete and describe a significant class of finite monoids for which the problem is tractable.

Related projects

• Institute for Theoretical Computer Science
• Mathematical structures and their physical applications
• Algebraic Methods in Automata and Formal Language Theory