---
abstract: |
    For an efficient implementation of Buchberger’s Algorithm, it is essential to avoid the treatment of as many unnecessary critical pairs or obstructions as possible. In the case of the commutative polynomial ring, this is achieved by the Gebauer-Möller criteria. Here we present an adaptation of the Gebauer-Möller criteria for non-commutative polynomial rings, i.e. for free associative algebras over fields. The essential idea is to detect unnecessary obstructions using other obstructions with or without overlap. Experiments show that the new criteria are able to detect almost all unnecessary obstructions during the execution of Buchberger’s procedure.

    [**Keywords:**]{} Gröbner basis, free associative algebra, obstruction, Buchberger procedure

    [**AMS classification:**]{} 16-08, 20-04, 13P10
author:
- |
    Martin Kreuzer[^1], Xingqiang Xiu[^2]\
    Fakultät für Informatik und Mathematik\
    Universität Passau, D-94030 Passau, Germany
title: 'Non-Commutative Gebauer-Möller Criteria'
---

Introduction {#sec1}
============

Ever since B. Buchberger’s thesis [@Bu65], Gröbner bases have become a fundamental tool for computations in commutative algebra and algebraic geometry. The most time-consuming part in Buchberger’s Algorithm is the computation of the normal remainder of an S-polynomial corresponding to a critical pair. Therefore a significant amount of energy has been spent on reducing the number of critical pairs which have to be treated. 