Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Ulla Koppenhagen; Ernst W. Mayr 
Titel:
The Complexity of the Boundedness, Coverability, and Selfcoverability Problems for Commutative Semigroups 
Abstract:
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,...    »
 
Stichworte:
Selfcoverability Problem; Computational Complexity; Polynomial Ideals 
Jahr:
1995 
Jahr / Monat:
1995-05-01 00:00:00 
Seiten/Umfang:
11