The Complexity of the Coverability, the Containment, and the Equivalence Problems for Commutative Semigroups

Ulla Koppenhagen and Ernst W. Mayr


In this paper, we present optimal decision procedures for the coverability, the containment, and the equivalence problems for commutative semigroups. These procedures require at most space 2cn, where n is the size of the problem instance, and c is some problem independent constant.

Our results close the gap between the 2c'nlog(n) space upper bound, shown by Rackoff for the coverability problem and shown by Huynh for the containment and the equivalence problems, and the exponential space lower bound resulting from the corresponding bound for the uniform word problem established by Mayr and Meyer.

We establish the exponential space completeness of the coverability, the containment and the equivalence problems for commutative semigroups.