A Circuit-Based Approach to Efficient Enumeration

Amarilli, Antoine; Bourhis, Pierre; Jachiet, Louis; Mengel, Stefan

Type de document :

Communication dans un congrès avec actes

DOI :

10.4230/LIPIcs.ICALP.2017.111

Titre :

A Circuit-Based Approach to Efficient Enumeration

Auteur(s) :

Amarilli, Antoine [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Bourhis, Pierre [Auteur]

Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Jachiet, Louis [Auteur]
Types and Reasoning for the Web [TYREX]
Mengel, Stefan [Auteur]
Centre de Recherche en Informatique de Lens [CRIL]

Éditeur(s) ou directeur(s) scientifique(s) :

Ioannis Chatzigiannakis
Piotr Indyk
Anca Muscholl

Titre de la manifestation scientifique :

ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming

Ville :

Varsovie

Pays :

Pologne

Date de début de la manifestation scientifique :

2017-07-10

Mot(s)-clé(s) en anglais :

constant-delay
enumeration
d-DNNFs
MSO
circuits

Discipline(s) HAL :

Informatique [cs]/Base de données [cs.DB]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-01639179/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01639179/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01639179/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

LIPIcs-ICALP-2017-111.pdf
Accès libre
Accéder au document

document
Accès libre
Accéder au document

LIPIcs-ICALP-2017-111.pdf
Accès libre
Accéder au document

A Circuit-Based Approach to Efficient Enumeration BibTeX CSV Excel RIS

Fichiers

A Circuit-Based Approach to Efficient Enumeration

BibTeX

CSV

Excel

RIS