Advertisement
Published in:
2006 | OriginalPaper | Chapter
Matching Modulo Superdevelopments Application to Second-Order Matching
Author : Germain Faure
Published in: Logic for Programming, Artificial Intelligence, and Reasoning
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
To perform higher-order matching, we need to decide the
βη
-equivalence on
λ
-terms. The first way to do it is to use simply typed
λ
-calculus and this is the usual framework where higher-order matching is performed. Another approach consists in deciding a restricted equivalence based on finite superdevelopments. We consider higher-order matching modulo this equivalence over untyped
λ
-terms for which we propose a terminating, sound and complete matching algorithm.
This is in particular of interest since all second-order
β
-matches are matches modulo superdevelopments. We further propose a restriction to second-order matching that gives exactly all second-order matches.