Polygraphs : from rewriting to higher categories / Dimitri Ara [and five others].

Format:

Book

Author/Creator:

Ara, Dimitri, author.

Series:

London Mathematical Society lecture note series ; 495.

London Mathematical Society lecture note series ; 495

Language:

English

Subjects (All):

Categories (Mathematics).

Physical Description:

1 online resource (xx, 648 pages) : digital, PDF file(s).

Edition:

First edition.

Place of Publication:

Cambridge : Cambridge University Press, 2025.

Summary:

This is the first book to revisit the theory of rewriting in the context of strict higher categories, through the unified approach provided by polygraphs, and put it in the context of homotopical algebra. The first half explores the theory of polygraphs in low dimensions and its applications to the computation of the coherence of algebraic structures. Illustrated with algorithmic computations on algebraic structures, the only prerequisite in this section is basic category theory. The theory is introduced step-by-step, with detailed proofs. The second half introduces and studies the general notion of n-polygraph, before addressing the homotopy theory of these polygraphs. It constructs the folk model structure on the category on strict higher categories and exhibits polygraphs as cofibrant objects. This allows the formulation of higher-dimensional generalizations of the coherence results developed in the first half. Graduate students and researchers in mathematics and computer science will find this work invaluable.

Contents:

Cover

Series information

Title page

Imprints page

Contents

Preface

Part I Fundamentals of Rewriting

1 Abstract Rewriting and 1-Dimensional Polygraphs

1.1 The Category of 1-Polygraphs

1.2 Presenting Sets

1.3 Abstract Rewriting Systems

1.4 Decreasing Diagrams

2 Two-Dimensional Polygraphs

2.1 Generating Categories and Groupoids

2.2 The Category of 2-Polygraphs

2.3 Presenting Categories

2.4 Generating 2-Categories

2.5 Coherent Confluence of 1-Polygraphs

3 Operations on Presentations

3.1 Limits and Colimits of Presented Categories

3.2 Localizations of Presented Categories

3.3 Distributive Laws

4 String Rewriting and 2-Polygraphs

4.1 String Rewriting Systems

4.2 Deciding Equality

4.3 Critical Branchings

4.4 Reduction Orders

4.5 Constructing Presentations of Categories

4.6 Residuation

5 Tietze Transformations and Completion

5.1 Tietze Transformations

5.2 The Knuth-Bendix Completion Procedure

5.3 Universality of Finite Convergent Rewriting

6 Linear Rewriting

6.1 Linear Rewriting

6.2 Rewriting Properties of Linear Polygraphs

6.3 Linear Bases Induced by Monomial Orders

6.4 Historical Account of Linear Rewriting

Part II Coherent Presentations

7 Coherence by Convergence

7.1 Acyclic Extensions

7.2 Coherent Presentations

7.3 Coherent Confluence

7.4 Tietze Transformations of (3, 1)-Polygraphs

7.5 Coherent Completion and Reduction

7.6 Coherent Presentations of Associative Algebras

8 Categories of Finite Derivation Type

8.1 Finite Derivation Type

8.2 Convergence and Finite Derivation Type

8.3 Identities Among Relations

9 Homological Syzygies and Confluence

9.1 Monoids of Finite Homological Type

9.2 Monoids Having Homological Type Left-FP[sub(2)]

9.3 Homological Type Left-FP[sub(3)] and Confluence.

Part III Diagram Rewriting

10 Three-Dimensional Polygraphs

10.1 Three-Dimensional Polygraphs

10.2 Rewriting Properties of 3-Polygraphs

10.3 Constructing Presentations

10.4 Indexed Critical Branchings

10.5 Distributive Laws

11 Termination of 3-Polygraphs

11.1 Reduction and Termination Orders

11.2 Functorial Interpretations

11.3 Termination by Derivations

12 Coherent Presentations of 2-Categories

12.1 Coherent Presentations of 2-Categories

12.2 Squier's Completion of 3-Polygraphs

12.3 (3, 2)-PROs

12.4 Coherence in Monoidal Categories

12.5 Coherence in Symmetric and Braided Monoidal Categories

13 Term Rewriting Systems

13.1 Presentations of Lawvere Theories

13.2 More on Models

13.3 Term Rewriting

13.4 Term Rewriting Systems and 3-Polygraphs

13.5 Cartesian Polygraphs

Part IV Polygraphs

14 Higher Categories

14.1 Globular Sets

14.2 Strict n-Categories

14.3 Basic Examples

14.4 More Properties of Cat[sub( )]

14.5 (n, p)-Categories

15 Polygraphs

15.1 Main Definitions

15.2 Three Adjunctions

15.3 (n, p)-Polygraphs

16 Properties of the Category of n-Polygraphs

16.1 Limits and Colimits

16.2 Morphisms in Pol[sub( )]

16.3 Is Pol[sub(n)] a Topos?

16.4 Local Presentability

16.5 Contexts

16.6 Basis Uniqueness

16.7 Rewriting Properties of n-Polygraphs

16.8 Polygraphs With Finite Derivation Type

17 A Catalogue of n-Polygraphs

17.1 First Examples of n-Polygraphs

17.2 Tensoring Polygraphs by O[sub(1)]

17.3 Families of Polygraphs

17.4 Construction of Polygraphs via Steiner's Theory

18 Generalized Polygraphs

18.1 T-Polygraphs

18.2 Polygraphs for Weak n-Categories

18.3 Linear Polygraphs

Part V Homotopy Theory of Polygraphs

19 Polygraphic Resolutions

19.1 Weak Factorization Systems.

19.2 Cofibrations and Trivial Fibrations

19.3 Polygraphic Resolutions

19.4 Uniqueness of Polygraphic Resolutions

20 Toward the Folk Model Structure: -Equivalences

20.1 -Equivalences

20.2 The -Category of Cylinders

20.3 The -Category of Reversible Cylinders

20.4 Coherent Reversible Cells and Fibrations

20.5 Immersions

21 The Folk Model Structure

21.1 The Folk Model Structure on Cat[sub( )]

21.2 The Path Objects of Cylinders

21.3 The Folk Model Structure on Cat[sub(n)] and Cat[sub(n,p)]

22 Homology of -Categories

22.1 The Abelianization Functor

22.2 Deriving the Abelianization Functor

22.3 Comparison With Homology of Monoids

22.4 Examples

23 Resolutions by ( ,1)-Polygraphs

23.1 Polygraphic Resolutions and Contractions

23.2 Polygraphic Resolutions From Convergence

23.3 Abelianization of Polygraphic Resolutions

23.4 Categories of Finite Homological Type

23.5 Homological Syzygies and Identities Among Relations

Appendices

Appendix A A Catalogue of 2-Polygraphs

A.1 Presentations of Monoids

A.2 Presentations of Categories

Appendix B Examples of Coherent Presentations of Monoids

B.1 Artin Monoids

B.2 Plactic and Chinese Monoids

Appendix C A Catalogue of 3-Polygraphs

C.1 Braids and Symmetries

C.2 Monoids

C.3 Distributive Laws

C.4 Bialgebras

C.5 Coefficients

C.6 Frobenius Algebras

C.7 Linear Relations

C.8 Interchange

C.9 Idempotent Objects

C.10 Dualities

C.11 Endomorphisms

C.12 Nets

C.13 Simplicial and Cubical Categories

C.14 Quantum Processes

Appendix D A Syntactic Description of Free n-Categories

D.1 A Syntax for n-Categories

D.2 Alternative Syntax for n-Categories

D.3 The Word Problem for Free n-Categories

Appendix E Complexes and Homology

E.1 Modules Over a Ring

E.2 Chain Complexes.

E.3 Resolutions

E.4 Homology of Monoids

Appendix F Homology of Categories

F.1 Simplicial Homology and Nerve of a Category

F.2 Homology of Categories With Coefficients

F.3 Categories of Finite Homological Type

Appendix G Locally Presentable Categories

G.1 Sketches

G.2 Locally Presentable Categories

G.3 Essentially Algebraic Theories

Appendix H Model Categories

H.1 Definition

H.2 The Homotopy Category

H.3 Derived Functors

References

Index of Symbols

Subject Index.

Notes:

Title from publisher's bibliographic system (viewed on 19 Mar 2025).

Includes bibliographical references.

ISBN:

9781009498975

1009498975

9781009498968

1009498967

OCLC:

1514627400