The Complexity of the Boundedness, Coverability, and Selfcoverability Problems for Commutative Semigroups
Ulla Koppenhagen, Ernst W Mayr · 1995
In this paper, efficient decision procedures for the boundedness, coverability and selfcoverability 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 constant independent of n. Furthermore, we show that this space requirement is inevitable: any decision procedure for these problems requires at least exponential space. Thus, we establish the exponential space completeness of the boundedness, coverability and selfcoverability problems for commutative semigroups.