|
|
|
|
|
Problems connected with polynomial ideals generated by finite sets of multivariate polynomials occur, as mathematical subproblems, in a number of different areas of computer science. A technique that provides algorithmic solutions to a variety of these problems is the method of Gröbner bases. In this thesis, we present an optimal exponential space algorithm for generating the reduced Gröbner basis of binomial ideals. Applying this algorithm, we establish the exponential space completeness of the following problems for commutative semigroups, or equivalently, reversible Petri nets, which are well-known models for parallel processes: the coverability problem (in a generalized form), the finite enumeration problem, the boundedness problem, the finite containment problem, the finite equivalence problem, the subword problem (in a generalized form), the containment problem, and the equivalence problem.
We use the close relationship between commutative semigroups and pure difference binomial ideals. Based on the algorithm of Mayr and Meyer for the uniform word problem in commutative semigroups, we first derive an exponential space algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals. Then this algorithm is extended to an exponential space algorithm for generating the reduced Gröbner basis of general binomial ideals over the rational numbers. By the results of Mayr and Meyer, and of Huynh, which give a doubly exponential lower bound (in the size of the problem instance) for the maximal degree of the elements of Gröbner bases of pure difference binomial ideals, these algorithms are space optimal.
As applications of the algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals, we derive procedures solving several problems for commutative semigroups. The first application provides a solution for a generalization of the ordinary coverability problem. Given a word u, it generates a closed representation of the set of all words from which u can be covered. In the case of finite congruence classes, it is shown that this procedure enumerates the elements of the congruence class under consideration. Subsequently, procedures for the boundedness problem, the finite containment and the finite equivalence problems for commutative semigroups are derived.
A further block of applications of the algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals starts with an algorithm for a general form of the ordinary subword problem for commutative semigroups. The uniform word problem and the ordinary coverability problem are special cases of our formulation of the subword problem. The procedure presented also provides a solution for the boundedness problem and beyond that can be used to investigate some characterizations of the considered congruence class such as bounded variables or extreme minimal periods.
The main idea of our algorithms for commutative semigroups is to construct a basis of a pure difference binomial ideal such that the reduced Gröbner basis of this ideal contains the solution. All presented procedures operate in work space exponential in the size of the problem instance. It is shown that the exponential space hardness of the considered problems follows from the work of Mayr and Meyer. Thus, the presented algorithms are space optimal.
Finally, we derive from the above results an algorithm that constructs for commutative semigroups a closed representation of a given congruence class as a uniformly semilinear set. We exhibit an exponential space upper bound for the containment and the equivalence problems for commutative semigroups. Thus, the gap between the previously known upper space bound of 2d n log(n) shown by Huynh (with n the size of the problem instance and d > 0 some constant independent of n) and the exponential space lower bound (exponential space hardness) resulting from the exponential space completeness of the uniform word problem is closed. The exponential space completeness of the containment problem and the equivalence problem for commutative semigroups is established.