Some results on confluence: decision and what to do without - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Some results on confluence: decision and what to do without

Résumé

We recall first some decidability results on the confluence of TRS, and related properties about unicity of normal forms. In particular we put it in perspective old proofs of undecidability of confluence for the class of flat systems with more recent results, in order to discuss the importance of linearity wrt these decision problems. Second, we describe a case study on musical rhythm notation involving modeling rewrite systems which are not confluent. In this case, instead of applying rewrite rules directly, we enumerate the equivalence class of a given term using automata-based representations and dynamic programming.
Fichier principal
Vignette du fichier
confluenceno.pdf (318.45 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01367535 , version 1 (16-09-2016)

Identifiants

  • HAL Id : hal-01367535 , version 1

Citer

Florent Jacquemard. Some results on confluence: decision and what to do without. 5th International Workshop on Confluence, Beniamino Accattoli, Ashish Tiwari Sep 2016, Obergurgl, Austria. ⟨hal-01367535⟩
194 Consultations
134 Téléchargements

Partager

Gmail Facebook X LinkedIn More