Publication details

Complexity issues of checking identities in finite monoids

Investor logo

KLÍMA Ondřej

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

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

More info