Polygraphs: from rewriting to higher categories
This book revisits the theory of rewriting in the context of strict higher categories, through the unified approach via polygraphs, and puts it in the context of homotopical algebra. The book is divided into two parts, namely, low-dimensional book consisting of three parts (Chapters 1--6, Chapters 7--9 and Chapters 10--13) and higher-dimensional book consisting of two parts (Chapters 14--18 and Chapters 19--23).\N\NThe synopsis of the book goes as follows.\N\N\begin{itemize}\N\item[Chapter 1] discusses 1-polygraphs, which are simply directed graphs, thought in this paper as abstract rewriting systems.\N\N\item[Chapter 2] is dedicated to the definition of 2-polygraphs, which are a 2-dimensional generalization of 1-polygraphs presented in the previous chapter.\N\N\item[Chapter 3] takes a modular approach, by combining already known presentations, to show that a given polygraph is a presentation of a given category.\N\N\item[Chapter 4] recasts the notion of string rewriting system into the language of polygraphs.\N\N\item[Chapter 5] introduces a notion of \textit{Tietze transformation} for 2-polygraphs, generalizing the one introduced in \S 1.2 for 1-polygraphs. Tietze transformations in combinatorial group theory are explained in detail in [\textit{R. C. Lyndon} and \textit{P. E. Schupp}, Combinatorial group theory. Berlin-Heidelberg-New York: Springer-Verlag (1977; Zbl 0368.20023); \textit{W. Magnus} et al., Combinatorial group theory. Presentations of groups in terms of generators and relations. 2nd rev. ed. New York: Dover Publications, Inc. (1976; Zbl 0362.20023)].\N\N\item[Chapter 6] presents rewriting techniques for associative algebras. \S 6.1 introduces linear polygraphs as a framework for linear rewriting. \S 6.2 studies the confluence properties of linear polygraphs. \S 6.3 expresses Gröbner bases and PBW bases in the setting of linear polygraphs.\N\N\item[Chapter 7] sees a canonical and efficient way to extend a convergent presentation of a category \(C\)\ by a 2-polygraph \(P\)\ into a coherent one. Precisely, the 3-cells used in this extension procedure are in one-to-one correspondence with the confluence diagrams of critical branchings in \(P\)\ (Theorem 7.3.5).\N\N\item[Chapter 8] is concerned with the homotopical finiteness condition introduced by \textit{C. C. Squier} et al. [Theor. Comput. Sci. 131, No. 2, 271--294 (1994; Zbl 0863.68082)]. It is shown (Theorem 8.1.2) that if a category \(C\)\ admits a finite presentation \(P\)\ of \textit{finite derivation type} (FDT) then all finite presentations of \(C\)\ are of finite derivation type.\N\N\item[Chapter 9] is concerned wtih the homological finiteness condition (\textit{homological type left-FP}\(_{3}\)) investigated by \textit{C. C. Squier} [J. Pure Appl. Algebra 49, 201--217 (1987; Zbl 0648.20045)]. It is shown (Theorem 9.3.4) that for a monoid, the property of having FDT implies the property of having left-FP\(_{3}\).\N\N\item[Chapter 10] establishes 3-polygraphs as a notion of presentation for 2-categories (\S 10.1). \S 10.2 defines the notion of critical branching along with the proof that confluence of critical branchings implies the local confluence of the polygraph. \S 10.3 explains how to show that a given 3-polygraph is a presentation of a given 2-category. \S 10.4 shows that a finite convergent polygraph might give rise to an infinite number of critical branchings. \S 10.5 provides some techniques for combining presentations of 2-categories and for building presentations of 2-categories in a modular way.\N\N\item[Chapter 11] presents techniques for proving the termination of 3-polygraphs, generalizing those already introduced for 2-polygraphs in \S 4.4.\N\N\item[Chapter 12] generalizes the definitions and results of Chapter 7 from categories to 2-categories after [\textit{Y. Guiraud} and \textit{P. Malbos}, Theory Appl. Categ. 22, 420--478 (2009; Zbl 1190.18002); Math. Struct. Comput. Sci. 22, No. 6, 931--969 (2012; Zbl 1264.18007)].\N\N\item[Chapter 13] briefly revisits term rewriting systems from a polygraphic viewpoint. \S 13.1 introduces term rewriting systems as presentations of Lawvere theories. \S 13.2 recalls some classical results in Lawvere theories. \S 13.3 defines rewriting steps, critical branchings and the original Knuth-Bendix completion procedure [\textit{D. E. Knuth} and \textit{P. B. Bendix}, Proc. Conf. Oxford 1967, 263--297 (1970; Zbl 0188.04902)]. \S 13.4 shows that a term rewriting system can be described by a 3-polygraph in which variables are handled explicitly. \S 13.5 gives a precise meaning to the statement that term rewriting systems are cartesian polygraphs.\N\N\item[Chapter 14] starts with a description of the presheaf category \(\boldsymbol{Glob}_{\omega}\)\ of globular sets, defining a family of operations rigging a globular set with a structure of \(\omega\)-category. It is then established that the category \(\boldsymbol{Cat}_{\omega}\)\ of strict \(\omega\)-categories is exactly the category of algebras of the monad introduced by the forgetful functor from \(\boldsymbol{Cat}_{\omega}\)\ to \(\boldsymbol{Glob}_{\omega}\). Important subcategories of \(\boldsymbol{Cat}_{\omega}\)\ obtained by requiring cells to be invertible above a given dimension are finally defined.\N\N\item[Chapter 15] deals with the particular case where the finitary monad \(T\)\ on globular sets comes from the adjunction between \(\boldsymbol{Cat}_{\omega}\)\ and \(\boldsymbol{Glob}_{\omega}\).\N\N\item[Chapter 16] establishes the main properties of the category \(\boldsymbol{Pol}_{n}\)\ of \(n\)-polygraphs.\N\N\item[Chapter 17] concentrates on Street's \textit{orientals} [\textit{R. Street}, J. Pure Appl. Algebra 49, 283--335 (1987; Zbl 0661.18005)]. Two methods for generating the above families are explained. The first one is based on a direct definition of the cylinder polygraph \(\mathbb{Q}_{1}\otimes P\)\ of a polygraph \(P\). The second is based on Steiner's theory of augmented directed complexes [\textit{R. Steiner}, Homology Homotopy Appl. 6, No. 1, 175--200 (2004; Zbl 1071.18005)].\N\N\item[Chapter 18] starts with the presentation of \textit{M. A. Batanin}'s ideas [Contemp. Math. 230, 37--57 (1998; Zbl 0932.18004)] concerned with a generalization of the notion of polygraph to that of \(T\)-polygraph, the key point being the fairly general adjunction result (\S 18.1.5). Two key examples are presented, namely, the monad of weak \(n\)-categories (\S 18.2) and the monad associated to linear polygraphs (\S 18.3.1).\N\N\item[Chapter 19] aims to introduce the notion of a polygraphic resolution of an \(\omega\)-category, which was introduced by \textit{F. Métayer} [Theory Appl. Categ. 11, 148--184 (2003; Zbl 1020.18001)] to define a homology theory for \(\omega\)-categories, that is now known as \textit{polygraphic homology}. Roughly speaking, a polygraphic resolution is a non-abelian version of a resolution of a module in the sense of homological algebra.\N\N\item[Chapter 20] introduces all the notions and tools allowing of defining and establishing the existence of the \textit{folk model category} on \(\boldsymbol{Cat}_{\omega}\)\ presented in the coming section.\N\N\item[Chapter 21] establishes the existence of what is called the folk model category structure on on \(\boldsymbol{Cat}_{\omega}\) after \textit{Y. Lafont} et al. [Adv. Math. 224, No. 3, 1183--1231 (2010; Zbl 1236.18017)].\N\N\item[Chapter 22] establishes that the polygraphic homology is the left derived functor of a linearization functor from \(\boldsymbol{Cat}_{\omega}\)\ to the category \(\boldsymbol{Ch}_{\mathbb{Z},\geqslant0}\)\ of chain complexes.\N\N\item[Chapter 23] shows how to construct a polygraphic resolution of a category from a convergent presentation of that category and how to deduce an abelian version of such a resolution.\N\N\item[Appendix A] lists some examples of presentations of monoids and categories.\N\N\item[Appendix B] presents examples of coherent presentations of monoids in the sense developed in Chapter 7.\N\N\item[Appendix C] presents some examples of presentations of 2-categories by 3-polygraphs.\N\N\item[Appendix D] provides an explicit description of the free \(n\)-category \(P^{\ast}\)\ generated by an \(n\)-polygraph \(P\).\N\N\item[Appendix E] recalls basic notions on modules, abelian resolutions, and homology.\N\N\item[Appendix F] is concerned with homology of categories.\N\N\item[Appendix G] is a quick introduction to locally presentable categories, referring the reader to the classical book [\textit{J. Adámek} and \textit{J. Rosický}, Locally presentable and accessible categories. Cambridge: Cambridge University Press (1994; Zbl 0795.18007)] for a detailed presentation.\N\N\item[Appendix H] gathers the main definitions plus some complements on model category structure.\N\end{itemize}
- Equivalences in diagrammatic sets
- Hom -categories of a computad are free
- -weak equivalences between weak -categories
- Rewriting techniques for relative coherence
- Higher catoids, higher quantales and their correspondences
- An (, 0)-model structure on Eilenberg-Zilber opetopic sets
- Rewriting modulo in diagrammatic algebras and application to categorification
This page was built for publication: Polygraphs: from rewriting to higher categories
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7035825)
