Item


Anti-unification for unranked terms and hedges

We study anti-unification for unranked terms and hedges that may contain term and hedge variables. The anti-unification problem of two hedges -1 and -2 is concerned with finding their generalization, a hedge q such that both -1 and -2 are instances of q 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 restricting possible alternatives permitted in the generalizations. The restrictions are imposed with the help of a rigidity function, which is a parameter in the improved algorithm and selects certain common subsequences from the hedges to be generalized. The obtained rigid anti-unification algorithm is further made more precise by permitting combination of hedge and term variables in generalizations. Finally, we indicate a possible application of the algorithm in software engineering

This research has been partially supported by the Spanish Ministerio de Economía 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

© Journal of Automated Reasoning, 2014, vol. 52, núm. 2, p. 155-190

Springer Verlag

Author: Kutsia, Temur
Levy, Jordi
Villaret i Ausellé, Mateu
Date: 2014 February
Abstract: We study anti-unification for unranked terms and hedges that may contain term and hedge variables. The anti-unification problem of two hedges -1 and -2 is concerned with finding their generalization, a hedge q such that both -1 and -2 are instances of q 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 restricting possible alternatives permitted in the generalizations. The restrictions are imposed with the help of a rigidity function, which is a parameter in the improved algorithm and selects certain common subsequences from the hedges to be generalized. The obtained rigid anti-unification algorithm is further made more precise by permitting combination of hedge and term variables in generalizations. Finally, we indicate a possible application of the algorithm in software engineering
This research has been partially supported by the Spanish Ministerio de Economía 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
Format: application/pdf
Citation: https://doi.org/10.1007/s10817-013-9285-6
ISSN: 0168-7433 (versió paper)
1573-0670 (versió electrònica)
Document access: http://hdl.handle.net/10256/14444
Language: eng
Publisher: Springer Verlag
Collection: MINECO/PN 2013-2015/TIN2012-33042
MINECO/PN 2011-2013/TIN2010-20967-C04-01
AGAUR/2009-2013/2009 SGR-1434
Reproducció digital del document publicat a: https://doi.org/10.1007/s10817-013-9285-6
Articles publicats (D-IMA)
Is part of: © Journal of Automated Reasoning, 2014, vol. 52, núm. 2, p. 155-190
Rights: Attribution 3.0 Spain
Rights URI: http://creativecommons.org/licenses/by/3.0/es/
Subject: Algorismes computacionals
Computer algorithms
Lògica matemàtica
Logic, Symbolic and mathematical
Complexitat computacional
Computational complexity
Title: Anti-unification for unranked terms and hedges
Type: info:eu-repo/semantics/article
Repository: DUGiDocs

Subjects

Authors