The Complexity of the Equivalence Problem for Commutative Semigroups

In this paper, optimal decision procedures for the equivalence, subword, and finite enumeration problems for commutative semigroups are obtained. These procedures require at most space 2^{cn}, where n is the size of the problem instance, and c is some problem independent constant. Furthermore, we show that this space requirement is inevitable: any decision procedure for these problems requires at least exponential space in the worst case, the equivalence, subword, and finite enumeration problems for commutative semigroups are exponential space complete. For the equivalence problem, our results close the gap between the 2^{c'nlog(n)} space upper bound shown by Huynh [Huy85] and the exponential space lower bound resulting from the corresonding bound for the uniform word problem established in [MM82].     «

In this paper, optimal decision procedures for the equivalence, subword, and finite enumeration problems for commutative semigroups are obtained. These procedures require at most space 2^{cn}, where n is the size of the problem instance, and c is some problem independent constant. Furthermore, we show that this space requirement is inevitable: any decision procedure for these problems requires at least exponential space in the worst case, the equivalence, subword, and finite enumeration problems...     »