Alarcón, B.; Emmes, F.; Fuhs, C.; Giesl, J.; Gutiérrez Gil, R.; Lucas Alba, S.; Schneider-Kamp, P.... (2008). Improving Context-Sensitive Dependency Pairs. Lecture Notes in Computer Science. 5330:636-651. https://doi.org/10.1007/978-3-540-89439-1_44
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/202272
Title:
|
Improving Context-Sensitive Dependency Pairs
|
Author:
|
Alarcón, Beatriz
Emmes, Fabian
Fuhs, Carsten
Giesl, Jürgen
Gutiérrez Gil, Raúl
Lucas Alba, Salvador
Schneider-Kamp, Peter
Thiemann, René
|
UPV Unit:
|
Universitat Politècnica de València. Escuela Politécnica Superior de Alcoy - Escola Politècnica Superior d'Alcoi
Universitat Politècnica de València. Escola Tècnica Superior d'Enginyeria Informàtica
|
Issued date:
|
|
Abstract:
|
[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 ...[+]
[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.
[-]
|
Subjects:
|
Automated termination proofs
,
Proving termination
,
Rewrite systems
,
Transformation
,
Framework
|
Copyrigths:
|
Reserva de todos los derechos
|
Source:
|
Lecture Notes in Computer Science. (issn:
0302-9743
)
|
DOI:
|
10.1007/978-3-540-89439-1_44
|
Publisher:
|
Springer-Verlag
|
Publisher version:
|
https://doi.org/10.1007/978-3-540-89439-1_44
|
Project ID:
|
info:eu-repo/grantAgreement/DFG//GI 274%2F5-2/
...[+]
info:eu-repo/grantAgreement/DFG//GI 274%2F5-2/
info:eu-repo/grantAgreement/MEC//HA 2006-0007/
info:eu-repo/grantAgreement/MEC//TIN2007-68093-C02-02/
info:eu-repo/grantAgreement/MEC//TIN2004-7943-C04-02/
info:eu-repo/grantAgreement/MCIU//AP2005-3399//Ayudas para la formación de Profesorado Universitario (FPU)/
info:eu-repo/grantAgreement/DAAD//D%2F06%2F12785/
[-]
|
Thanks:
|
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 ...[+]
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.
[-]
|
Type:
|
Artículo
|