A Circuit-Based Approach to Efficient Enumeration

Antoine Amarilli 1 Pierre Bourhis 2, 3 Louis Jachiet 4 Stefan Mengel 5
2 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
4 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We study the problem of enumerating the satisfying valuations of a circuit while bounding the delay, i.e., the time needed to compute each successive valuation. We focus on the class of structured d-DNNF circuits originally introduced in knowledge compilation, a sub-area of artificial intelligence. We propose an algorithm for these circuits that enumerates valuations with linear preprocessing and delay linear in the Hamming weight of each valuation. Moreover, valuations of constant Hamming weight can be enumerated with linear preprocessing and constant delay. Our results yield a framework for efficient enumeration that applies to all problems whose solutions can be compiled to structured d-DNNFs. In particular, we use it to recapture classical results in database theory, for factorized database representations and for MSO evaluation. This gives an independent proof of constant-delay enumeration for MSO formulae with first-order free variables on bounded-treewidth structures.
Type de document :
Communication dans un congrès
Ioannis Chatzigiannakis; Piotr Indyk; Anca Muscholl. ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, Jul 2017, Varsovie, Poland. pp.1-15, 〈10.4230/LIPIcs.ICALP.2017.111〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01639179
Contributeur : Pierre Bourhis <>
Soumis le : lundi 20 novembre 2017 - 12:47:48
Dernière modification le : jeudi 11 octobre 2018 - 08:48:04
Document(s) archivé(s) le : mercredi 21 février 2018 - 13:21:10

Fichier

LIPIcs-ICALP-2017-111.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Antoine Amarilli, Pierre Bourhis, Louis Jachiet, Stefan Mengel. A Circuit-Based Approach to Efficient Enumeration . Ioannis Chatzigiannakis; Piotr Indyk; Anca Muscholl. ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, Jul 2017, Varsovie, Poland. pp.1-15, 〈10.4230/LIPIcs.ICALP.2017.111〉. 〈hal-01639179〉

Partager

Métriques

Consultations de la notice

774

Téléchargements de fichiers

45