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

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.

  • Activities

    • 1 Participation in conference
    • 1 Oral presentation

    35th International Conference on Logic Programming

    Gonzague Yernaux (Participant)

    20 Sep 201925 Sep 2019

    Activity: Participating in or organising an event typesParticipation in conference

    Anti-unification in Constraint Logic Programming

    Gonzague Yernaux (Speaker)

    22 Sep 2019

    Activity: Talk or presentation typesOral presentation

    Cite this