The method of Buchberger allows to effectively solve the membership problem in polynomial ideals and many other interesting problems. Mayr and Meyer showed that this is very expensive in the worst case. So the problem has to be specialized for more efficient computations. As previous results show, the complexity of the membership problem is mainly related to the degrees of the representation problem and Gröbner bases which are studied in the first part of the thesis. The main contributions are upper and lower bounds for Gröbner bases depending on the ideal dimension and some results for toric ideals. In the second part, these findings are applied to questions of complexity. The presentation comprises an incremental space-efficient algorithm for the computation of Gröbner bases, an algorithm in polylogarithmic space for the membership problem in toric ideals and the space-efficient computation of the radicals of low-dimensional ideals.     «

The method of Buchberger allows to effectively solve the membership problem in polynomial ideals and many other interesting problems. Mayr and Meyer showed that this is very expensive in the worst case. So the problem has to be specialized for more efficient computations. As previous results show, the complexity of the membership problem is mainly related to the degrees of the representation problem and Gröbner bases which are studied in the first part of the thesis. The main contributions ar...     »

Mit Buchberger's Algorithmus lässt sich u.a. das Membership-Problem in Polynomidealen effektiv lösen. Mayr und Meyer haben jedoch gezeigt, dass dies im schlimmsten Fall sehr aufwendig ist. Deshalb müssen einfache Spezialfälle des Problems identifiziert werden. Bekannterweise hängt die Komplexität des Membership-Problems primär von den Graden des Darstellungsproblems und der Gröbner-Basen ab, welche im ersten Teil dieser Arbeit betrachtet werden. Die wichtigsten Beiträge sind Gradschranken für Gröbner-Basen in Abhängigkeit von der Dimension des Ideals und Schranken für torische Ideale. Im zweiten Teil der Arbeit wird darauf aufbauend die Komplexität diverser Algorithmen beschrieben. Diese umfassen die inkrementelle platzeffiziente Berechnung von Gröbner-Basen, einen Algorithums in polylogarithmischem Platz für das Membership-Problem in torischen Idealen und die platzeffiziente Berechnung von Radikalen von niedrigdimensionalen Idealen.     «

Mit Buchberger's Algorithmus lässt sich u.a. das Membership-Problem in Polynomidealen effektiv lösen. Mayr und Meyer haben jedoch gezeigt, dass dies im schlimmsten Fall sehr aufwendig ist. Deshalb müssen einfache Spezialfälle des Problems identifiziert werden. Bekannterweise hängt die Komplexität des Membership-Problems primär von den Graden des Darstellungsproblems und der Gröbner-Basen ab, welche im ersten Teil dieser Arbeit betrachtet werden. Die wichtigsten Beiträge sind Gradschranken für...     »