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

Algebraic Analysis of Parallel Process Models

Ernst W. Mayr

We first consider binomial ideals over the rationals in the unknowns x₁,...,x_n. It is known that Gröbner bases for such ideals are again binomial and obey a doubly exponential degree bound. We use this bound and another doubly exponential degree bound (due to Hermann/26) for the word problem for finitely presented commutative semigroups to derive exponential space bounds for the following problems:

	the subword reachability problem in finitely presented commutative semigroups;
	the problem of computing the minimal elements of an equivalence class in a finitely presented commutative semigroup;
	the problem of computing the periods of an equivalence class in a finitely presented commutative semigroup;
	the equivalence problem for finitely presented commutative semigroups;
	the problem of computing the reduced Gröbner basis for a binomial ideal.

These bounds provide the first exact complexity bounds for Gröbner basis computation and for the representation of the state set of reversible Petri nets.