Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

The Complexity of the Boundedness, Coverability, and Selfcoverability Problems for Commutative Semigroups

Ulla Koppenhagen and Ernst W. Mayr

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.