Polygraphs of finite derivation type - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Mathematical Structures in Computer Science Année : 2018

Polygraphs of finite derivation type

Résumé

Craig Squier proved that, if a monoid can be presented by a finite convergent string rewriting system, then it satisfies the homological finiteness condition left-FP3. Using this result, he constructed finitely presentable monoids with a decidable word problem, but that cannot be presented by finite convergent rewriting systems. Later, he introduced the condition of finite derivation type, which is a homotopical finiteness property on the presentation complex associated to a monoid presentation. He showed that this condition is an invariant of finite presentations and he gave a constructive way to prove this finiteness property based on the computation of the critical branchings: being of finite derivation type is a necessary condition for a finitely presented monoid to admit a finite convergent presentation. This survey presents Squier's results in the contemporary language of polygraphs and higher-dimensional categories, with new proofs and relations between them.
Fichier principal
Vignette du fichier
ihdr.pdf (411.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00932845 , version 1 (17-01-2014)
hal-00932845 , version 2 (13-12-2016)

Identifiants

Citer

Yves Guiraud, Philippe Malbos. Polygraphs of finite derivation type. Mathematical Structures in Computer Science, 2018, 28 (2), pp.155-201. ⟨10.1017/S0960129516000220⟩. ⟨hal-00932845v2⟩
545 Consultations
233 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More