Book contents
- Frontmatter
- Contents
- Preface
- Part I Fundamentals Of Rewriting
- 1 Abstract Rewriting and 1-Dimensional Polygraphs
- 2 Two-Dimensional Polygraphs
- 3 Operations on Presentations
- 4 String Rewriting and 2-Polygraphs
- 5 Tietze Transformations and Completion
- 6 Linear Rewriting
- Part II Coherent Presentations
- Part III Diagram Rewriting
- Part IV Polygraphs
- Part V Homotopy Theory of Polygraphs
- Appendices
- References
- Index of Symbols
- Subject Index
5 - Tietze Transformations and Completion
from Part I - Fundamentals Of Rewriting
Published online by Cambridge University Press: 18 March 2025
- Frontmatter
- Contents
- Preface
- Part I Fundamentals Of Rewriting
- 1 Abstract Rewriting and 1-Dimensional Polygraphs
- 2 Two-Dimensional Polygraphs
- 3 Operations on Presentations
- 4 String Rewriting and 2-Polygraphs
- 5 Tietze Transformations and Completion
- 6 Linear Rewriting
- Part II Coherent Presentations
- Part III Diagram Rewriting
- Part IV Polygraphs
- Part V Homotopy Theory of Polygraphs
- Appendices
- References
- Index of Symbols
- Subject Index
Summary
In this chapter, a notion of Tietze transformation for 2-polygraphs is introduced, consisting of elementary operations on 2-polygraphs that preserve the presented category, such that any two finite 2-polygraphs presenting the same category can be transformed into one another by applying such transformations. By using Tietze transformations, the goal is to turn a given presentation of a category into another one that possesses better computational properties. In particular, the Knuth-Bendix completion procedure applies those transformations to turn a presentation into a confluent one. Convergent presentations lead to a solution of the word problem: for those, the equivalence between two words is immediately decided by comparing their normal forms.To tackle the word problem for an arbitrary presentation, a good strategy consists in trying to transform it into a convergent one by using Tietze transformations. From this point of view, a natural question arises as to whether a finite presentation of a category with decidable word problem can always be turned into a convergent one by applying Tietze transformations: this problem is called "universality of convergent presentations".
- Type
- Chapter
- Information
- Polygraphs: From Rewriting to Higher Categories , pp. 103 - 125Publisher: Cambridge University PressPrint publication year: 2025