Non-commutative Gröbner Bases and Applications

  • Commutative Gröbner bases have a lot of applications in theory and practice, because they have many nice properties, they are computable, and there exist many efficient improvements of their computations. Non-commutative Gröbner bases also have many useful properties. However, applications of non-commutative Gröbner bases are rarely considered due to high complexity of computations. The purpose of this study was to improve the computation of non-commutative Gröbner bases and investigate the applications of non-commutative Gröbner bases. Gröbner basis theory in free monoid rings was carefully revised and Gröbner bases were precisely characterized in great detail. For the computations of Gröbner bases, the Buchberger Procedure was formulated. Three methods, say interreduction on obstructions, Gebauer-Möller criteria, and detecting redundant generators, were developed for efficiently improving the Buchberger Procedure. Further, the same approach was applied to study Gröbner basis theory in free bimodules over free monoid rings. The Buchberger Procedure was also formulated and improved in this setting. Moreover, J.-C. Faugere's F4 algorithm was generalized to this setting. Finally, many meaningful applications of non-commutative Gröbner bases were developed. Enumerating procedures were proposed to semi-decide some interesting undecidable problems. All the examples in the thesis were computed using the package gbmr of the computer algebra system ApCoCoA. The package was developed by the author. It contains dozens of functions for Gröbner basis computations and many concrete applications. The package gbmr and a collection of interesting examples are available at

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Author:Xingqiang Xiu
Advisor:Martin Kreuzer
Document Type:Doctoral Thesis
Year of Completion:2012
Date of Publication (online):2012/07/25
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2012/07/23
Release Date:2012/07/25
Tag:Gebauer-Möller; applications; non-commutative Gröbner basis; non-commutative polynomial; optimization
GND Keyword:Assoziativer Ring; Endlich erzeugter Modul; Gruppentheorie; Gröbner-Basis
Institutes:Fakultät für Informatik und Mathematik / Sonstiger Autor der Fakultät für Informatik und Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
open_access (DINI-Set):open_access
Licence (German):License LogoStandardbedingung laut Einverständniserklärung

$Rev: 13581 $