Activities per year
Abstract
Antiunification in logic programming refers to the process of capturing common syntactic structure among given goals, computing a single new goal that is more general called a generalization of the given goals. Finding an arbitrary common generalization for two goals is trivial, but looking for those common generalizations that are either as large as possible (called largest common generalizations) or as specific as possible (called most specific generalizations) is a nontrivial optimization problem, in particular when goals are considered to be unordered sets of atoms. In this work we provide an indepth study of the problem by defining two different generalization relations. We formulate a characterization of what constitutes a most specific generalization in both settings. While these generalizations can be computed in polynomial time, we show that when the number of variables in the generalization needs to be minimized, the problem becomes NPhard. We subsequently revisit an abstraction of the largest common generalization when antiunification is based on injective variable renamings, and prove that it can be computed in polynomially bounded time.
Original language  English 

Title of host publication  Proceedings of the 30th EACSL Annual Conference on Computer Science Logic (CSL 2022) 
Editors  Florin Manea, Alex Simpson 
Number of pages  17 
ISBN (Electronic)  9783959772181 
DOIs  
Publication status  Published  27 Jan 2022 
Event  Computer Science Logic 2022  Göttingen, Germany Duration: 14 Feb 2022 → 19 Feb 2022 http://csl2022.unigoettingen.de/ 
Publication series
Name  Leibniz International Proceedings in Informatics (LIPIcs) 

Volume  216 
ISSN (Electronic)  18688969 
Conference
Conference  Computer Science Logic 2022 

Abbreviated title  CSL 2022 
Country/Territory  Germany 
City  Göttingen 
Period  14/02/22 → 19/02/22 
Internet address 
Keywords
 Antiunification
 Logic Programming
 NPcompleteness
 Time complexity
 Algorithms
 Inductive Logic Programming
Fingerprint
Dive into the research topics of 'Antiunification of Unordered Goals'. Together they form a unique fingerprint.
Computer Science Logic 2022
Gonzague Yernaux (Participant) & Wim VANHOOF (Participant)
14 Feb 2022 → 19 Feb 2022Activity: Participating in or organising an event types › Participation in conference

Antiunification of Unordered Goals
Gonzague Yernaux (Speaker)
18 Feb 2022Activity: Talk or presentation types › Oral presentation