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
1 - Abstract Rewriting and 1-Dimensional Polygraphs
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
This chapter discusses 1-polygraphs, which are simply directed graphs, thought of here as abstract rewriting systems: they consist of vertices, which represent the objects of interest, and arrows, which indicate that one object can be rewritten into another. After formally introducing those, it will be shown that they provide a notion of presentation for sets, by generators and relations. Of course presentations of sets are of little interest in themselves, but merely used here as a gentle introduction to some of the main concepts discussed in this work: in particular, the notion of Tietze transformations is introduced, which generates the equivalence between two presentations of the same set. In this context, an important question consists in deciding when two objects are equivalent, i.e., represent the same element of the presented set. In order to address it, the theory of abstract rewriting systems is developed.
Keywords
- Type
- Chapter
- Information
- Polygraphs: From Rewriting to Higher Categories , pp. 3 - 21Publisher: Cambridge University PressPrint publication year: 2025