Term Rewriting with Prefix Context Constraints and Bottom-Up StrategiesReport as inadecuate

Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies - Download this document for free, or read online. Document in PDF available to download.

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 3 Sakabe Sakai Lab, Department of Computer Science and Mathematical Informatics, Graduate School of Information Science 4 Nagoya University

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.

Author: Florent Jacquemard - Yoshiharu Kojima - Masahiko Sakai -

Source: https://hal.archives-ouvertes.fr/


Related documents