Complexity issues of checking identities in finite monoids

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. 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:

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