1 Search Results for "Yernaux, Gonzague"

Anti-Unification of Unordered Goals

Authors: Gonzague Yernaux and Wim Vanhoof

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Anti-unification 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 non-trivial optimization problem, in particular when goals are considered to be unordered sets of atoms. In this work we provide an in-depth 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 NP-hard. We subsequently revisit an abstraction of the largest common generalization when anti-unification is based on injective variable renamings, and prove that it can be computed in polynomially bounded time.

Cite as

Gonzague Yernaux and Wim Vanhoof. Anti-Unification of Unordered Goals. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

  author =	{Yernaux, Gonzague and Vanhoof, Wim},
  title =	{{Anti-Unification of Unordered Goals}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{37:1--37:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.37},
  URN =		{urn:nbn:de:0030-drops-157574},
  doi =		{10.4230/LIPIcs.CSL.2022.37},
  annote =	{Keywords: Anti-unification, Logic programming, NP-completeness, Time complexity, Algorithms, Inductive logic programming}
  • Refine by Author
  • 1 Vanhoof, Wim
  • 1 Yernaux, Gonzague

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 1 Algorithms
  • 1 Anti-unification
  • 1 Inductive logic programming
  • 1 Logic programming
  • 1 NP-completeness
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail