Linear Rewriting
Dimitri Ara, Albert Burroni, Yves Guiraud, Philippe Malbos, François Métayer, Samuel Mimram · Cambridge University Press eBooks · 2025
This chapter presents rewriting techniques for associative algebras. Here, algorithms are sought to turn a given presentation by generators and relations into a rewriting system by orienting the latter, thereby producing linear bases of the presented algebra. In particular, this approach applies to various fundamental decision problems, such as the word problem, ideal membership, or to compute quadratic bases, e.g., Poincaré-Birkhoff-Witt bases, Hilbert series, syzygies of presentations, homology groups, and Poincaré series. However, if rewriting rules are required to be compatible with the linear structure, an immediate problem arises: no rewriting system can be terminating. In order to fix this problem, the structure of linear polygraph with an appropriate notion of reduction can be considered. Linear polygraphs are introduced as a framework for linear rewriting, their confluence properties are studied, and Gröbner bases and Poincaré-Birkhoff-Witt bases are expressed in the setting of linear polygraphs.