Complexity issues of checking identities in finite monoids

Warning

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

Authors	KLÍMA Ondřej
Year of publication	2009
Type	Article in Periodical
Magazine / Source	Semigroup Forum
MU Faculty or unit	Faculty of Science
Citation
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