Efficient Enumeration of Solutions Produced by Closure Operations

Abstract : In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure by polymorphisms of a boolean relation with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations" (e.g. by union, intersection, difference, symmetric difference ...). To do so, we prove that for any set of operations F, one can decide in polynomial time whether an element belongs to the closure by F of a family of sets. When the relation is over a domain larger than two elements, we prove that our generic enumeration method fails, since the associated decision problem is NP-hard.
Type de document :
Communication dans un congrès
33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, Feb 2016, Orléans, France. 47, 2016, LIPIcs. 〈10.4230/LIPIcs.STACS.2016.52〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01388505
Contributeur : Marie-France Sagot <>
Soumis le : mardi 23 mai 2017 - 09:39:00
Dernière modification le : jeudi 19 avril 2018 - 14:49:47
Document(s) archivé(s) le : vendredi 25 août 2017 - 00:22:53

Fichier

increm2.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Arnaud Mary, Yann Strozecki. Efficient Enumeration of Solutions Produced by Closure Operations. 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, Feb 2016, Orléans, France. 47, 2016, LIPIcs. 〈10.4230/LIPIcs.STACS.2016.52〉. 〈hal-01388505〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

22