Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies

Florent Jacquemard 1, 2 Yoshiharu Kojima 3 Masahiko Sakai 4
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
Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, IRCAM, CNRS - Centre National de la Recherche Scientifique
Abstract : We consider the extension of term rewriting rules with context constraints restricting the application of rewriting to positions whose prefix (i.e. the sequence of symbols from the rewrite position up to the root) belongs to a given regular language. This approach, well studied in the case of string rewriting, is similar to node selection mechanisms in XML transformation languages, and also generalizes the context-sensitive rewriting. The systems defined this way are called prefix constrained TRS (pCTRS), and we study the decidability of reachability of regular tree model checking and the preservation of regularity for some subclasses. The two latter properties hold for linear and right-shallow standard TRS but not any-more when adding context constraints. We show that these properties can be restored by restricting derivations to bottom-up ones, and moreover that it implies that left-linear and right-ground pCTRS preserve regularity and have a decidable regular model checking problem.
Type de document :
Communication dans un congrès
Amy P. Felty and Aart Middeldorp. 25th International Conference on Automated Deduction (CADE’15), Aug 2015, Berlin, Germany. Springer, LNCS
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01149319
Contributeur : Florent Jacquemard <>
Soumis le : mercredi 13 mai 2015 - 18:32:45
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : jeudi 20 avril 2017 - 00:00:20

Fichier

pCTRS-bu.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01149319, version 2

Collections

Citation

Florent Jacquemard, Yoshiharu Kojima, Masahiko Sakai. Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies. Amy P. Felty and Aart Middeldorp. 25th International Conference on Automated Deduction (CADE’15), Aug 2015, Berlin, Germany. Springer, LNCS. 〈hal-01149319v2〉

Partager

Métriques

Consultations de la notice

188

Téléchargements de fichiers

113