Anti-unification in Constraint Logic Programming. Issue 5 (September 2019)

• Record Type: Journal Article
• Authors: YERNAUX, GONZAGUE; VANHOOF, WIM
• Is Part Of: Theory and practice of logic programming. Volume 19:Issue 5/6(2019)
• Page Start: 773
• Page End: 789
• Publication Date: 2019-09
• Subjects: Anti-unification, -- (most specific) generalization, -- CLP, -- program analysis; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068419000188
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: Anti-unification refers to the process of generalizing two (or more) goals into a single, more general, goal that captures some of the structure that is common to all initial goals. In general one is typically interested in computing what is often called a most specific generalization, that is a generalization that captures a maximal amount of shared structure. In this work we address the problem of anti-unification in CLP, where goals can be seen as unordered sets of atoms and/or constraints. We show that while the concept of a most specific generalization can easily be defined in this context, computing it becomes an NP-complete problem. We subsequently introduce a generalization algorithm that computes a well-defined abstraction whose computation can be bound to a polynomial execution time. Initial experiments show that even a naive implementation of our algorithm produces acceptable generalizations in an efficient way.