Identity checking problem for transformation monoids

Warning

This publication doesn't include Institute of Computer Science. 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:	Institute for Theoretical Computer Science Mathematical structures and their physical applications Algebraic Methods in Automata and Formal Language Theory II