Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Proving Termination of Context-Sensitive Rewriting with MU-TERM

  • Alarcón, Beatriz
  • Iborra, José
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Context-sensitive rewriting (CSR) is a restriction of rewriting which forbids reductions on selected arguments of functions. Proving termination of CSR is an interesting problem with several applications in the fields of term rewriting and programming languages. Several methods have been developed for proving termination of CSR. The new version of MU-TERM which we present here implements all currently known techniques. Furthermore, we show how to combine them to furnish MU-TERM with an expert which is able to automatically perform the termination proofs. Finally, we provide a first experimental evaluation of the tool., This work has been partially supported by the EU (FEDER) and the Spanish MEC, under grants TIN2004-7943-C04-02 and HA 2006-0007, the Generalitat Valenciana under grant GV06/285, and the ICT for EU-India Cross-Cultural Dissemination ALA/95/23/2003/077-054 project. Beatriz Alarc¿on was partially supported by the Spanish MEC under FPU grant AP2005-3399.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Context-Sensitive Dependency Pairs

  • Alarcón, Beatriz
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Termination is one of the most interesting problems when dealing with context-sensitive rewrite systems. Although there is a good number of techniques for proving termination of context-sensitive rewriting (CSR), the dependency pair approach, one of the most powerful techniques for proving termination of rewriting, has not been investigated in connection with proofs of termination of CSR. In this paper, we show how to use dependency pairs in proofs of termination of CSR. The implementation and practical use of the developed techniques yield a novel and powerful framework which improves the current state-of-the-art of methods for proving termination of CSR., This work has been partially supported by the EU (FEDER) and the Spanish MEC, under grant TIN 2004-7943-C04-02, the Generalitat Valenciana under grant GV06/285, and the ICT for EU-India Cross-Cultural Dissemination ALA/95/23/2003/077-054 project. Beatriz Alarcón was partially supported by the Spanish MEC under FPU grant AP2005-3399.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Usable Rules for Context-Sensitive Rewrite Systems

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Urbain, Xavier
[EN] Recently, the dependency pairs (DP) approach has been generalized to context-sensitive rewriting (CSR). Although the context-sensitive dependency pairs (CS-DP) approach provides a very good basis for proving termination of CSR, the current developments basically correspond to a ten-years-old DP approach. Thus, the task of adapting all recently introduced dependency pairs techniques to get a more powerful approach becomes an important issue. In this direction, usable rules are one of the most interesting and powerful notions. Actually usable rule have been investigated in connection with proofs of innermost termination of CSR. However, the existing results apply to a quite restricted class of systems. In this paper, we introduce a notion of usable rules that can be used in proofs of termination of CSR with arbitrary systems. Our benchmarks show that the performance of the CS-DP approach is much better when such usable rules are considered in proofs of termination of CSR., Work partially supported by the EU (FEDER) and the Spanish MEC, under grants TIN 2004-7943-C04-02, TIN 2007-68118-C02 and HA 2006-0007.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Context-Sensitive Dependency Pairs

  • Alarcón, Beatriz
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Termination is one of the most interesting problems when dealing with context-sensitive rewrite systems. Although a good number of techniques for proving termination of context-sensitive rewriting (CSR) have been proposed so far, the adaptation to CSR of the dependency pair approach, one of the most powerful techniques for proving termination of rewriting, took some time and was possible only after introducing some new notions like collapsing dependency pairs, which are specific for CSR. In this paper, we develop the notion of context-sensitive dependency pair (CSDP) and show how to use CSDPs in proofs of termination of CSR. The implementation and practical use of the developed techniques yield a novel and powerful framework which improves the current state-of-the-art of methods for automatically proving termination of CSR. (c) 2010 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN, under Grants TIN 2007-68093-C02 and HA 2006-0007. Beatriz Alarcon was partially supported by the Spanish MEC/MICINN under FPU Grant AP2005-3399. Raul Gutierrez was partially supported by the Spanish MEC/MICINN Grant TIN 2004-7943-C04-02.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Improving the Context-Sensitive Dependency Graph

  • Alarcón, Beatriz
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] The dependency pairs method is one of the most powerful technique for proving termination of rewriting and it is currently central in most automatic termination provers. Recently, it has been adapted to be used in proofs of termination of context-sensitive rewriting. The use of collapsing dependency pairs i.e., having a single variable in the right-hand side is a novel and essential feature to obtain a correct framework in this setting. Unfortunately, dependency pairs behave as a kind of glue in the context-sensitive dependency graph which makes the cycles bigger, thus making some proofs of termination harder. In this paper we show that this effect can be safely mitigated by removing some arcs from the graph, thus leading to faster and easier proofs. Narrowing dependency pairs is also introduced and used here to eventually simplify the treatment of the context-sensitive dependency graph. We show the practicality of the new techniques with some benchmarks., This work has been partially supported by the EU (FEDER) and the Spanish MEC, under grants TIN2004-7943-C04-02 and HA 2006-0007, the Generalitat Valenciana under grant GV06/285, and the ICT for EU-India Cross-Cultural Dissemination ALA/95/23/2003/077-054 project. Beatriz Alarc¿on was partially supported by the Spanish MEC under FPU grant AP2005-3399.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Improving Context-Sensitive Dependency Pairs

  • Alarcón, Beatriz
  • Emmes, Fabian
  • Fuhs, Carsten
  • Giesl, Jürgen
  • Schneider-Kamp, Peter
  • Thiemann, René
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Context-sensitive dependence pairs (CS-DPs) are currently the most powerful method for automated termination analysis of context-sensitive rewriting. However, compared to DPs for ordinary rewriting, CS-DPs suffer from two main drawbacks: (a) CS-DPs can be collapsing. This complicates the handling of CS-DPs and makes them less powerful in practice. (b) There does not exist a "DP framework" for CS-DPs which would allow one to apply them in a flexible and modular way. This paper solves drawback (a) by introducing a new definition of CS-DPs. With our definition, CS-DPs are always non-collapsing and thus, they can be handled like ordinary DPs. This allows us to solve drawback (b) as well, i.e., we extend the existing DP framework for ordinary DPs to context sensitive rewriting. We implemented our results in the tool AProVE and successfully evaluated them on a large collection of examples., Authors from Valencia were partially supported by the EU (FEDER) and the Spanish MEC/MICINN, under grants TIN 2007-68093-C02-02 and HA 2006-0007. B. Alarcón was partially supported by the Spanish MEC/MICINN under FPU grant AP2005-3399. R. Gutiérrez was partially supported by the Spanish MEC/MICINN, under grant TIN 2004-7943-C04-02. Authors from Aachen were supported by the DAAD under grant D/06/12785 and by the DFG under grant GI 274/5-2.