Identity checking problem for transformation monoids

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KLÍMA Ondřej

Year of publication 2012
Type Article in Periodical
Magazine / Source Semigroup Forum
MU Faculty or unit

Faculty of Science

Citation
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:

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

More info