The Equational Theory of Aperiodic Semigroups is Decidable in Exponential Time

Due to a result by McCammond (Int. J. Algebra Comput. 2001) it is decidable whether all aperiodic semigroups satisfy some given identity of ω -terms. The respective decision procedure works by computing normal forms, but unfortunately neither its worst-case running time nor the maximal size of the intermediate terms have been estimated. We pursue a different approach and solve the same problem by means of first-order definability of regular languages and an infinite Ehrenfeucht-Fraïssé game on ω -terms. In this way, we obtain an algorithm which decides whether a given identity of ω -terms holds in all aperiodic semigroups and whose running time is exponential in the size of the ω -terms. This result was obtained in the course of developing a framework which allows for separating the bookkeeping involved in winning strategies for Ehrenfeucht-Fraïssé games on finite words from the actual strategy.

Authors

• Martin Huschenbett

Keywords

No keywords are indexed for this paper.