Rewriting Systems on Arbitrary Monoids

Eduardo Magalhães · 2026

Read Rewriting Systems on Arbitrary Monoids by Eduardo Magalhães (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10564.txt.

Introduction

Eduardo Magalhães studies rewriting, the step-by-step replacement of symbols by fixed rules. Classic rewriting works on strings of symbols, which form a free monoid. He asks what happens when the rules act inside any monoid at all. A push for this comes from logic, since free monoids cannot be pinned down by first-order axioms.

He defines monoidal rewriting systems, where each reduction step takes place inside a chosen ambient monoid. To study them, he builds a 2-category of systems that always halt and never fork into rival results. The work gives rewriting theory a broader, more abstract home. It may help logicians apply first-order tools to rewriting problems.

Catalog record

CREATOREduardo Magalhães
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10564

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Rewriting Systems on Arbitrary Monoids Eduardo Magalhães Abstract . In this paper, we introduce monoidal rewriting systems (MRS), an abstraction of string rewriting in which reductions are defined over an arbitrary ambient monoid rather than a free monoid of words. This shift is partly motivated by logic: the class of free monoids is not first-order axiomatizable, so “working in the free setting” cannot be treated internally when applying first-order methods to rewriting presentations. To analyze these systems categorically, we define 𝐍𝐂𝐑𝐒 𝟐 \mathbf{NCRS_{2}} as the 2-category of Noetherian Confluent MRS. We then prove the existence of a canonical biadjunction between 𝐍𝐂𝐑𝐒 𝟐 \mathbf{NCRS_{2}} and 𝐌𝐨𝐧 \mathbf{Mon} . Finally, we classify all Noetherian Confluent MRS that present a given fixed monoid. For this, we introduce Generalized Elementary Tietze Transformations (GETTs) and prove that any two presentations of a monoid are connected by a (possibly infinite) sequence of these transformations, yielding a complete characterization of generating systems up to GETT-equivalence. 1. Introduction The study of rewriting systems has long occupied a central position at the intersection of theoretical computer science and algebra. Originating in the early 20th century with the work of Axel Thue [ 8 ] , these systems were developed to address fundamental decidability questions such as the word problem for semigroups and monoids (and, indirectly, groups). Over the decades, the theory has matured into a robust framework for analysing algebraic structures by algorithmic means. This field has been dominated by String Rewriting Systems (SRS), also known as semi-Thue systems. As detailed in the foundational work of Book and Otto ”String rewriting systems” [ 3 ] , an SRS is defined as a binary relation on a free monoid generated by some alphabet. When such a system is Noetherian and confluent, interpreting these relations as reduction rules allows one to rewrite complex words into unique irreducible forms, thereby offering a systematic approach to solving the word problem and other decidability problems. Parallel to the development of SRS, the theory of Abstract Rewriting Systems (ARS) emerged to abstract certain key properties of reduction such as confluence, local confluence, termination and so on. The key idea behind this abstraction is that, although when working with SRS we are rewriting words on free monoids, the study of properties such as termination and confluence does not, in general, depend on the specific free monoidal structure present. As surveyed by Terese in ”Term Rewriting Systems” [ 9 ] , ARS theory provides general notions of reduction relations and normal forms that are present not only when working with string rewriting but also term rewriting and lambda calculus. However, despite this high level of abstraction and countless uses in computer science, applications to the study of monoids have traditionally remained grounded to the free context: reductions are almost exclusively defined as transformations between words in a free monoid F_{A} , for some alphabet A . However, a structural limitation of classical rewriting systems is that they are intrinsically tied to free monoids. From a logical perspective, this creates a foundational mismatch: Let L=\{\cdot\} be the first-order language of monoids, and let K=\{\cdot,R\} be its expansion by a designated binary relation symbol. Given a monoid, its presentations by rewriting can naturally be interpreted as structures in the richer language K , while many structural questions about the monoid itself are most naturally stated in L . The caveat is that, in the classical setting, rewriting is restricted to free monoids, which are not first-order axiomatizable. As such, when interpreting a K -structure as a rewriting system, “freeness” cannot be treated internally and must be imposed as an external semantic condition. This observation suggests that, if one aims to use first-order/model-theoretic tools to study presentations of monoids, rewriting should be formulated intrinsically over arbitrary monoids (or at least over an elementary class of monoids). Motivated by these considerations, we introduce Monoidal Rewriting Systems (from here onward abbreviated as MRS), a generalization of string rewriting systems in which reductions are defined directly over an arbitrary monoid, rather than over a free monoid of words. When string rewriting systems are used to present a monoid, the essential property that underpins the process is simply the ability to compose elements, that is, the presence of a monoidal structure. From this perspective, the syntactic representation provided by words in a free monoid is not strictly necessary. By defining rewriting relations intrinsically on a monoid, we decouple rewriting from its traditional syntactic setting and obtain a notion of reduction that is internal to the algebraic structure itself. Furthermore, modern developments in category theory suggest that rewriting systems can be naturally understood not merely as static algebraic presentations, but as dynamic 2-dimensional structures, as exemplified by the theory of polygraphs and higher-dimensional word problems [ 1 , 4 ] . As emphasized in the work of Johnson and Yau [ 6 ] , 2-categories provide a natural language to describe transformations between morphisms, making them an ideal setting for formalizing relationships between different rewriting systems. Motivated by this perspective, the present work not only abstracts the underlying algebraic setting of rewriting from free to arbitrary monoids, but also organizes these systems within a strict 2-categorical framework, so that generating systems and their equivalences can be studied using inherently higher-dimensional, categorical tools. This paper is organized as follows: Section 2 sets some notation and reviews some of the preliminaries necessary for the rest of this work. In section 3, we define a monoidal rewriting system (MRS) as a triple (M,\cdot,R) where (M,\cdot) is a monoid and R\subseteq M\times M is a binary relation. We proceed by proving some small technical lemmas and results that are direct generalizations of basic known facts about SRS. One interesting fact about these lemmas is that their statements and proofs are essentially identical to those of their classical counterparts, which further strengthens the idea that the monoidal structure present in any SRS is the essential part that makes these lemmas work, and that the syntactic information that free monoids entail is not necessary at all. After this, we build the 2-category \mathbf{NCRS_{2}} of Noetherian confluent MRS and explore the existence of a biadjunction between this 2-category and the 2-category of monoids \mathbf{Mon} . The proof of this biadjunction is quite lengthy, and so we present it at the end in Appendix A. Finally, in section 4, we answer the question: Given a fixed monoid (M,\cdot) , what can be said about the family of Noetherian confluent MRS (A,\cdot,R) that present (M,\cdot) ? For this, we introduce the notion of a generalized elementary Tietze transformation (GETT) and prove that any two Noetherian confluent MRS that present the same monoid can be obtained from one another by a (possibly infinite) sequence of GETTs. 2. Preliminaries We assume familiarity with the basics of Abstract Rewriting Systems (ARS) as detailed in [ 9 ] . Given an ARS (A,\to) , we use \to^{*} to denote the reflexive transitive closure of \to , \leftrightarrow^{*} for the symmetric reflexive transitive closure of \to , and \bar{u} to denote the unique normal form of an element u in a Noetherian confluent ARS. Recall that an ARS (A,\to) is said to have the Church–Rosser property, if given a,b\in

Read the complete text