The Complexity of the Coverability, the
Containment, and the Equivalence Problems for Commutative
Semigroups
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.
