Complexity of Unification and Matching Problems in the Varieties of Bands
by
Ondřej Klíma
Masaryk University, Brno, Czech Republic

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 ba

We will also show that the matching problem is NP-complete for the variety of all bands although the complexity of the unification problem is unknown.

Date received: May 15, 2000

Copyright © 2000 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 Conferences Inc. Document # caec-33.