22 citations · 90 across the 29 of their papers we have counts for
4 papers · 1 filter
A Strongly Exponential Separation of DNNFs from CNF Formulas
Simone Bova, Florent Capelli, Stefan Mengel +1
Decomposable Negation Normal Forms (DNNFs) are Boolean circuits in negation normal form where the subcircuits leading into each AND gate are defined on disjoint sets of variables.…
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
Hubie Chen, Stefan Mengel
Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are the select-project-join queries. In this article, we study the fundamental probl…
Understanding model counting for -acyclic CNF-formulas
Johann Brault-Baron, Florent Capelli, Stefan Mengel
We extend the knowledge about so-called structural restrictions of by giving a polynomial time algorithm for -acyclic . In contrast to previous…
Hypergraph Acyclicity and Propositional Model Counting
Florent Capelli, Arnaud Durand, Stefan Mengel
We show that the propositional model counting problem #SAT for CNF- formulas with hypergraphs that allow a disjoint branches decomposition can be solved in polynomial time. We show…