|
Organizers |
Complexity Issues of Checking Identities in Finite Monoids
by
Ondrej Klima
Department of Algebra and Geometry, Masaryk University, Janackovo nam. 2a, Brno 662 95, Czech Republic
We study the computational complexity of checking identities in a fixed finite monoid. We show the smallest monoid for which this problem is coNP-complete and describe a significant class of finite monoids for which the problem is decidable in polynomial time. We also compare the complexities of this problem and the problem of solving equations in the same monoid.
Date received: May 21, 2004
Copyright © 2004 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # canq-84.