Reachability Analysis of Innermost Rewriting - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Reachability Analysis of Innermost Rewriting

Résumé

Approximating the set of terms reachable by rewriting finds more and more applications ranging from termination proofs of term rewriting systems, cryp- tographic protocol verification to static analysis of programs. However, since approximation techniques do not take rewriting strategies into account, they build very coarse approximations when rewriting is constrained by a specific strategy. In this work, we propose to adapt the Tree Automata Completion algorithm to accurately approximate the set of terms reachable by rewriting under the inner- most strategy. We prove that the proposed technique is sound and precise w.r.t. innermost rewriting. The proposed algorithm has been implemented in the Timbuk reachability tool. Experiments shows that it noticeably improves the accuracy of static analysis for functional programs using the call-by-value evaluation strategy. In particular, for some functional programs needing lazy evaluation to terminate, the computed approximations are precise enough to prove the absence of innermost normal forms, i.e. prove non termination of the program with call-by-value.
Fichier principal
Vignette du fichier
main.pdf (341.81 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00848260 , version 1 (25-07-2013)
hal-00848260 , version 2 (30-07-2013)
hal-00848260 , version 3 (30-07-2013)
hal-00848260 , version 4 (06-02-2014)
hal-00848260 , version 5 (10-02-2014)

Identifiants

  • HAL Id : hal-00848260 , version 5

Citer

Thomas Genet, Yann Salmon. Reachability Analysis of Innermost Rewriting. [Research Report] 2013. ⟨hal-00848260v5⟩
608 Consultations
217 Téléchargements

Partager

Gmail Facebook X LinkedIn More