Anti-Unification for Unranked Terms and Hedges
dc.contributor.author
dc.date.accessioned
2013-10-03T09:58:29Z
dc.date.available
2013-10-03T09:58:29Z
dc.date.issued
2011
dc.identifier.issn
1868-8969
dc.identifier.uri
dc.description.abstract
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
dc.description.sponsorship
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
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Dagstuhl Publishing
dc.relation
info:eu-repo/grantAgreement/MINECO//TIN2012-33042/ES/HERRAMIENTAS LOGICAS PARA PROBLEMAS COMBINATORIOS/
info:eu-repo/grantAgreement/MICINN//TIN2010-20967-C04-01/ES/TASSAT: TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL/
AGAUR/2009-2013/2009 SGR-1434
dc.relation.isformatof
Reproducció digital del document publicat a: http://dx.doi.org/10.4230/LIPIcs.RTA.2011.219
dc.relation.ispartof
Leibniz International Proceedings in Informatics (LIPPICS) : 22nd International Conference on Rewriting Techniques and Applications (RTA'11) : May 30 - June 1, 2011, Novi Sad, Serbia, 2011, vol. 10, P. 219-234
dc.relation.ispartofseries
Articles publicats (D-IMA)
dc.rights
Attribution-NonCommercial-NoDerivs 3.0 Spain
dc.rights.uri
dc.subject
dc.title
Anti-Unification for Unranked Terms and Hedges
dc.type
info:eu-repo/semantics/article
dc.rights.accessRights
info:eu-repo/semantics/openAccess
dc.embargo.terms
Cap
dc.type.version
info:eu-repo/semantics/publishedVersion
dc.identifier.doi
dc.identifier.idgrec
017114
dc.contributor.funder
dc.relation.ProjectAcronym