Connecting Knowledge Compilation Classes ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
Connecting Knowledge Compilation Classes and Width Parameters
Auteur(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Capelli, Florent [Auteur]
Linking Dynamic Data [LINKS]
Monet, Mikaël [Auteur]
Data, Intelligence and Graphs [DIG]
Senellart, Pierre [Auteur]
Value from Data [VALDA]
Data, Intelligence and Graphs [DIG]
Data, Intelligence and Graphs [DIG]
Capelli, Florent [Auteur]
Linking Dynamic Data [LINKS]
Monet, Mikaël [Auteur]
Data, Intelligence and Graphs [DIG]
Senellart, Pierre [Auteur]
Value from Data [VALDA]
Data, Intelligence and Graphs [DIG]
Titre de la revue :
Theory of Computing Systems
Éditeur :
Springer Verlag
Date de publication :
2020-08-01
ISSN :
1432-4350
Mot(s)-clé(s) en anglais :
Boolean circuits
d-DNNFs
OBDDs
Pathwidth
Knowledge compilation
Treewidth
d-DNNFs
OBDDs
Pathwidth
Knowledge compilation
Treewidth
Discipline(s) HAL :
Informatique [cs]
Résumé en anglais : [en]
The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. ...
Lire la suite >The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluationon databases, we obtain Boolean circuits that satisfy some width bounds, e.g., they have bounded treewidth or pathwidth. In this work, we give a systematic picture of many circuit classes considered in knowledge compilation and show how they can be systematically connected to width measures, through upper and lower bounds. Our upper bounds show that boundedtreewidth circuits can be constructively converted to d-SDNNFs, in time linear in the circuit size and singly exponential in the treewidth; and that bounded-pathwidth circuits can similarly be converted to uOBDDs. We show matching lower bounds on the compilation of monotone DNF or CNF formulas to structured targets, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable): any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth, and the same holds for uOBDDs (resp., n-OBDDs) when considering pathwidth. Unlike most previous work, our bounds apply to any formula of this class, not just a well-chosen family. Hence, we show that pathwidth and treewidth respectively characterize the efficiency of compiling monotone DNFs to uOBDDs and d-SDNNFs with compilation being singly exponential in the corresponding width parameter. We also show that our lower bounds on CNFs extend to unstructured compilation targets, with an exponential lower bound in the treewidth (resp., pathwidth) when compiling monotone CNFs of constant arity and degree to DNNFs (resp., nFBDDs).Lire moins >
Lire la suite >The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluationon databases, we obtain Boolean circuits that satisfy some width bounds, e.g., they have bounded treewidth or pathwidth. In this work, we give a systematic picture of many circuit classes considered in knowledge compilation and show how they can be systematically connected to width measures, through upper and lower bounds. Our upper bounds show that boundedtreewidth circuits can be constructively converted to d-SDNNFs, in time linear in the circuit size and singly exponential in the treewidth; and that bounded-pathwidth circuits can similarly be converted to uOBDDs. We show matching lower bounds on the compilation of monotone DNF or CNF formulas to structured targets, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable): any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth, and the same holds for uOBDDs (resp., n-OBDDs) when considering pathwidth. Unlike most previous work, our bounds apply to any formula of this class, not just a well-chosen family. Hence, we show that pathwidth and treewidth respectively characterize the efficiency of compiling monotone DNFs to uOBDDs and d-SDNNFs with compilation being singly exponential in the corresponding width parameter. We also show that our lower bounds on CNFs extend to unstructured compilation targets, with an exponential lower bound in the treewidth (resp., pathwidth) when compiling monotone CNFs of constant arity and degree to DNNFs (resp., nFBDDs).Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Projet ANR :
Collections :
Source :
Fichiers
- http://arxiv.org/pdf/1811.02944
- Accès libre
- Accéder au document
- 1811.02944
- Accès libre
- Accéder au document