Publication details

Identity checking problem for transformation monoids

Investor logo

KLÍMA Ondřej

Year of publication 2012
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 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:

You are running an old browser version. We recommend updating your browser to its latest version.

More info