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.     «

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,...     »