To access the full text documents, please follow this link: http://hdl.handle.net/10256/8402

Anti-Unification for Unranked Terms and Hedges
Kutsia, Temur; Levy, Jordi; Villaret i Ausellé, Mateu
We study anti-unification for unranked terms and hedges that may contain term and hedge variables. The anti-unification problem of two hedges S1 and S2 is concerned with finding their generalization, a hedge ǭ such that both S1 and S2 are instances of ǭ under some substitutions. Hedge variables help to fill in gaps in generalizations, while term variables abstract single (sub)terms with different top function symbols. First, we design a complete and minimal algorithm to compute least general generalizations. Then, we improve the efficiency of the algorithm by restrictingpossible alternatives permitted in the generalizations. The restrictions are imposed with the help of a rigidity function that is a parameter in the improved algorithm and selects certain common subsequences from the hedges to be generalized. Finally, we indicate a possible application of the algorithm in software engineering
This research has been partially supported by the Spanish Ministerio de Economa y Competitividad under the projects HeLo (TIN2012-33042) and TASSAT (TIN2010-20967-C04-01), by the EC FP6 for Integrated Infrastructures Initiatives under the project SCIEnce (contract No. 026133), by the Austrian Science Fund (FWF)under the project SToUT (P 24087-N18), and by the Generalitat de Catalunya under the grant AGAUR 2009-SGR-1434
Algorismes computacionals
Computer algorithms
Lògica matemàtica
Logic, Symbolic and mathematical
Complexitat computacional
Computational complexity
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Article
info:eu-repo/semantics/publishedVersion
Dagstuhl Publishing
         

Show full item record

Related documents

Other documents of the same author

Baumgartner, Alexander; Kutsia, Temur; Levy, Jordi; Villaret i Ausellé, Mateu
Levy, Jordi; Villaret i Ausellé, Mateu
López Ibáñez, Beatriz; Muñoz Solà, Víctor; Murillo Espinar, Javier; Barber, Federico; Salido, Miguel A.; Abril, Montserrat; Cervantes, Mariamar; Caro Pérez, Luis Fernando; Villaret i Ausellé, Mateu
Bofill Arasa, Miquel; Palahí i Sitges, Miquel; Suy Franch, Josep; Villaret i Ausellé, Mateu
 

Coordination

 

Supporters