Activities per year
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.
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.
Original language | English |
---|---|
Pages (from-to) | 773-789 |
Number of pages | 17 |
Journal | Theory and Practice of Logic Programming |
Volume | 19 |
Issue number | 5-6 |
DOIs | |
Publication status | Published - 20 Sept 2019 |
Keywords
- (most specific) generalization
- Anti-unification
- CLP
- program analysis
Fingerprint
Dive into the research topics of 'Anti-unification in Constraint Logic Programming'. Together they form a unique fingerprint.Projects
-
Algorithmic equivalence by generalization-driven transformations of logic programs
Yernaux, G. (PI) & Vanhoof, W. (Supervisor)
Project: PHD
-
Anti-unification in Constraint Logic Programming
Yernaux, G. (Speaker)
22 Sept 2019Activity: Talk or presentation types › Oral presentation
-
35th International Conference on Logic Programming
Yernaux, G. (Participant)
20 Sept 2019 → 25 Sept 2019Activity: Participating in or organising an event types › Participation in conference