### Abstract

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 |
---|---|

Number of pages | 16 |

Journal | Theory and Practice of Logic Programming |

DOIs | |

Publication status | Published - 20 Sep 2019 |

### Fingerprint

### Keywords

- Anti-unification
- generalization
- CLP
- program analysis

### Cite this

}

**Anti-unification in Constraint Logic Programming.** / Yernaux, Gonzague; Vanhoof, Wim.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Anti-unification in Constraint Logic Programming

AU - Yernaux, Gonzague

AU - Vanhoof, Wim

PY - 2019/9/20

Y1 - 2019/9/20

N2 - 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.

AB - 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.

KW - Anti-unification

KW - generalization

KW - CLP

KW - program analysis

U2 - http://dx.doi.org/10.1017/S1471068419000188

DO - http://dx.doi.org/10.1017/S1471068419000188

M3 - Article

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

ER -