Predicate Anti-unification in (Constraint) Logic Programming

Research output: Contribution in Book/Catalog/Report/Conference proceedingConference contribution

5 Downloads (Pure)


The concept of anti-unification refers to the process of determining the most specific generalization (msg) of two or more input program objects. In the domain of logic programming, anti-unification has primarily been investigated for computing msgs of tree-like program structures such as terms, atoms, and goals (the latter typically seen as ordered sequences).

In this work, we study the anti-unification of whole predicate definitions. We provide a definition of a predicate generalization that allows to characterize the problem of finding the most specific generalization of two predicates as a (computationally hard) search problem. The complexity stems from the fact that a correspondence needs to be constructed between (1) some of the arguments of each of the predicates, (2) some of the clauses in each of the predicate's definitions, and (3) some of the body atoms in each pair of associated clauses. We propose a working algorithm that simultaneously computes these correspondences in a greedy manner. While our algorithm does not necessarily compute the most specific generalization, we conjecture that it allows to compute, in general, a sufficiently good generalization in an acceptable time.
Original languageEnglish
Title of host publicationLogic-Based Program Synthesis and Transformation - 33rd International Symposium, LOPSTR 2023, Proceedings
Subtitle of host publicationLogic-Based Program Synthesis and Transformation. LOPSTR 2023.
EditorsRobert Glück, Bishoksan Kafle
PublisherSpringer, Cham
Number of pages19
ISBN (Electronic)978-3-031-45784-5
ISBN (Print)978-3-031-45783-8
Publication statusPublished - 16 Oct 2023
Event33rd International Symposium on Logic-based Program Synthesis and Transformation - Cascais, Lisbonne, Portugal
Duration: 23 Oct 202324 Oct 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14330 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference33rd International Symposium on Logic-based Program Synthesis and Transformation
Abbreviated titleLOPSTR 2023


  • Anti-unification
  • Generalization
  • Approximation algorithm
  • Approximation Algorithm


Dive into the research topics of 'Predicate Anti-unification in (Constraint) Logic Programming'. Together they form a unique fingerprint.

Cite this