LEA
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 2cn, 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.