Identity checking problem for transformation monoids

• Authors: KLÍMA Ondřej
• Year of publication: 2012
• Type: Article in Periodical
• Magazine / Source: Semigroup Forum
• MU Faculty or unit: Faculty of Science
• Doi: http://dx.doi.org/10.1007/s00233-012-9401-7
• Field: General mathematics
• Keywords: Checking identities; Finite semigroups; Complexity
• Description: We study the computational complexity of checking identities in a fixed finite monoid. We prove that this problem is coNP-complete for the monoid of all full transformations of a 4-element set. This result completes the description of the complexity of checking identities in the transformation monoids.

Related projects

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