Item


A Variant of Higher-Order Anti-Unification

We present a rule-based Huet’s style anti-unification algorithm for simply-typed lambda-terms in ɳ long β normal form, which computes a least general higher-order pattern generalization. For a pair of arbitrary terms of the same type, such a generalization always exists and is unique modulo α equivalence and variable renaming. The algorithm computes it in cubic time within linear space. It has been implemented and the code is freely available

Leibniz International Proceedings in Informatics (LIPPICS) : 24th International Conference on Rewriting Techniques and Applications (RTA 2013) : RTA 2013 : June 24-26 2013 : Eindhoven, The Netherlands, vol. 21, p. 113-127

Dagstuhl Publishing

Author: Baumgartner, Alexander
Kutsia, Temur
Levy, Jordi
Villaret i Ausellé, Mateu
Date: 2013
Abstract: We present a rule-based Huet’s style anti-unification algorithm for simply-typed lambda-terms in ɳ long β normal form, which computes a least general higher-order pattern generalization. For a pair of arbitrary terms of the same type, such a generalization always exists and is unique modulo α equivalence and variable renaming. The algorithm computes it in cubic time within linear space. It has been implemented and the code is freely available
Format: application/pdf
ISSN: 1868-8969
Document access: http://hdl.handle.net/10256/8403
Language: eng
Publisher: Dagstuhl Publishing
Collection: Reproducció digital del document publicat a: http://dx.doi.org/10.4230/LIPIcs.RTA.2013.113
Articles publicats (D-IMA)
Is part of: Leibniz International Proceedings in Informatics (LIPPICS) : 24th International Conference on Rewriting Techniques and Applications (RTA 2013) : RTA 2013 : June 24-26 2013 : Eindhoven, The Netherlands, vol. 21, p. 113-127
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
Title: A Variant of Higher-Order Anti-Unification
Type: info:eu-repo/semantics/article
Repository: DUGiDocs

Subjects

Authors