Complexity of unification and matching problems in the varieties of bands.
by
Ondřej Klíma
Department of Algebra and Geometry, Masaryk University, Brno

For a given variety of semigroups V we would like to find an algorithm which solves the problem whether a given system of equations with constants has a solution in a free semigroup in V. If the variety V is locally finite then this so called unification problem is trivially decidable and we can discuss the complexity aspects. Well known locally finite varieties of semigroups are the varieties of bands. For these varieties we are able to prove the following classification: Unification problem is in P for all subvarieties of the variety NB of all normal bands and is NP-complete for the other proper subvarieties of the variety of all bands.

We speak about matching problem if the equations have unknowns only on the left hand sides. The description of the complexity of the matching problem for the varieties of bands is the same as above if we replace the variety NB with the bigger variety RegB of all regular bands.

Date received: January 3, 2001