Some results on confluence: decision and what to do without

Florent Jacquemard 1, 2
1 Repmus - Représentations musicales
STMS - Sciences et Technologies de la Musique et du Son
2 MuTant - Synchronous Realtime Processing and Programming of Music Signals
UPMC - Université Pierre et Marie Curie - Paris 6, IRCAM, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : 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.
Type de document :
Communication dans un congrès
5th International Workshop on Confluence, Sep 2016, Obergurgl, Austria. 2016, Proceedings of the 5th International Workshop on Confluence
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01367535
Contributeur : Florent Jacquemard <>
Soumis le : vendredi 16 septembre 2016 - 12:34:56
Dernière modification le : mercredi 21 mars 2018 - 18:58:22
Document(s) archivé(s) le : samedi 17 décembre 2016 - 14:09:42

Fichier

confluenceno.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01367535, version 1

Collections

Citation

Florent Jacquemard. Some results on confluence: decision and what to do without. 5th International Workshop on Confluence, Sep 2016, Obergurgl, Austria. 2016, Proceedings of the 5th International Workshop on Confluence. 〈hal-01367535〉

Partager

Métriques

Consultations de la notice

256

Téléchargements de fichiers

72