Polygraphs of finite derivation type - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2014

Polygraphs of finite derivation type

Résumé

In 1987, 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 has constructed finitely presented decidable monoids that cannot be presented by finite convergent rewriting systems. In 1994, 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 self-contained survey presents those results in the contemporary language of polygraphs and higher-dimensional categories, providing new proofs and relations between them.
Fichier principal
Vignette du fichier
ihdr.pdf (463.93 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-00932845 , version 1

Citer

Yves Guiraud, Philippe Malbos. Polygraphs of finite derivation type. 2014. ⟨hal-00932845v1⟩
545 Consultations
233 Téléchargements

Partager

Gmail Facebook X LinkedIn More