Activités par an
Résumé
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.
langue originale | Anglais |
---|---|
titre | Proceedings of the 30th EACSL Annual Conference on Computer Science Logic (CSL 2022) |
rédacteurs en chef | Florin Manea, Alex Simpson |
Nombre de pages | 17 |
ISBN (Electronique) | 9783959772181 |
Les DOIs | |
Etat de la publication | Publié - 27 janv. 2022 |
Evénement | Computer Science Logic 2022 - Göttingen, Allemagne Durée: 14 févr. 2022 → 19 févr. 2022 http://csl2022.uni-goettingen.de/ |
Série de publications
Nom | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 216 |
ISSN (Electronique) | 1868-8969 |
Une conférence
Une conférence | Computer Science Logic 2022 |
---|---|
Titre abrégé | CSL 2022 |
Pays/Territoire | Allemagne |
La ville | Göttingen |
période | 14/02/22 → 19/02/22 |
Adresse Internet |
Empreinte digitale
Examiner les sujets de recherche de « Anti-unification of Unordered Goals ». Ensemble, ils forment une empreinte digitale unique.Projets
-
Equivalence algorithmique sur base de transformations axées sur la généralisation de programmes logiques
Yernaux, G. (Responsable du Projet) & Vanhoof, W. (Promoteur)
Projet: Projet de thèse
-
Anti-unification of Unordered Goals
Yernaux, G. (Orateur)
18 févr. 2022Activité: Discours ou présentation › Présentation orale
-
Computer Science Logic 2022
Yernaux, G. (Participant) & VANHOOF, W. (Participant)
14 févr. 2022 → 19 févr. 2022Activité: Participation ou organisation d'un événement › Participation à une conférence, un congrès