A cubical Squier's theorem

DOI10.1017/S0960129520000018MaRDI QIDQ5220186zbMATH OpenOpenAlexFDO

Authors Maxime Lucas

Publication date 11 March 2020

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06541

zbMATH Keywords

coherencerewritingcubical categories

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Sets with a single binary operation (groupoids) (20N02) Abstract and axiomatic homotopy theory in algebraic topology (55U35) Strict omega-categories, computads, polygraphs (18N30)

Abstract: Convergent rewriting systems are well-known tools in the study of the word-rewriting problem. In particular, a presentation of a monoid by a finite convergent rewriting system gives an algorithm to decide the word problem for this monoid. Squier proved that there exists a finitely presented monoid whose word problem was decidable but which did not admit a finite convergent presentation. To do so, Squier constructed, for any convergent presentation $(G,R)$ of a monoid $M$, a set of syzygies $S$ corresponding to relations between the relations. This construction was later extended into the construction of a polygraphic resolution $Sigma$ of $M$, whose first dimensions coincide with Squier's construction $(G,R,S)$. However, the construction of the polygraphic resolution has proved to be too complicated to be effectively computed on non-trivial examples. Cubical categories appear to be a promising framework where Squier's theorem and the construction of the polygraphic resolution would be more straightforward. This paper is the first step towards this goal. We start by defining the notion of $(2,k)$-cubical categories. We then adapt some classical notions of word rewriting to this cubical setting. Finally, we express and prove a cubical version of Squier's theorem.

Recommendations

• Polygraphs of finite derivation type
• On some homotopical and homological properties of monoid presentations.
• scientific article; zbMATH DE number 4210420
• A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
• Higher-dimensional normalisation strategies for acyclicity

Cites work

• scientific article; zbMATH DE number 3591054 (Why is no real title available?)
• scientific article; zbMATH DE number 1295627 (Why is no real title available?)
• scientific article; zbMATH DE number 1303765 (Why is no real title available?)
• scientific article; zbMATH DE number 2172968 (Why is no real title available?)
• A coherence theorem for pseudonatural transformations
• A finiteness condition for rewriting systems
• Coherence in monoidal track categories
• Cubical (, p)-categories
• Higher-dimensional normalisation strategies for acyclicity
• Higher-dimensional word problems with applications to equational logic
• Homomorphisms of higher categories
• Limits indexed by category-valued 2-functors
• Multiple categories: The equivalence of a globular and a cubical approach
• On the algebra of cubes
• Polygraphs of finite derivation type
• The algebra of oriented simplexes
• Word problems and a homological finiteness condition for monoids

Cited in

(4)

• Cubical (, p)-categories
• Single-set cubical categories and their formalisation with a proof assistant
• An effective seven cube theorem
• Higher catoids, higher quantales and their correspondences

This page was built for publication: A cubical Squier's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220186)