Anti-unification in Constraint Logic Programming

Research output: Contribution to journalArticle

3 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)773-789
Number of pages17
JournalTheory and Practice of Logic Programming
Volume19
Issue number5-6
DOIs
Publication statusPublished - 20 Sep 2019

Fingerprint

Constraint Logic Programming
Logic programming
Unification
Computational complexity
Polynomials
Atoms
Unordered
Computing
Experiments
Execution Time
Well-defined
NP-complete problem
Generalization
Polynomial
Experiment

Keywords

  • (most specific) generalization
  • Anti-unification
  • CLP
  • program analysis

Cite this

@article{f25a2b281a4a4072afaf8f8bae6876bf,
title = "Anti-unification in Constraint Logic Programming",
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.",
keywords = "(most specific) generalization, Anti-unification, CLP, program analysis",
author = "Gonzague Yernaux and Wim Vanhoof",
year = "2019",
month = "9",
day = "20",
doi = "https://doi.org/10.1017/S1471068419000188",
language = "English",
volume = "19",
pages = "773--789",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "5-6",

}

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

In: Theory and Practice of Logic Programming, Vol. 19, No. 5-6, 20.09.2019, p. 773-789.

Research output: Contribution to journalArticle

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 - (most specific) generalization

KW - Anti-unification

KW - CLP

KW - program analysis

UR - http://www.scopus.com/inward/record.url?scp=85072633181&partnerID=8YFLogxK

U2 - https://doi.org/10.1017/S1471068419000188

DO - https://doi.org/10.1017/S1471068419000188

M3 - Article

VL - 19

SP - 773

EP - 789

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 5-6

ER -