Linear Programs with Conjunctive Database Queries

Autor: Florent Capelli, Nicolas Crosetti, Joachim Niehren, Jan Ramon

Publikováno v: Logical Methods in Computer Science, Vol Volume 20, Issue 1 (2024)

In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying linear programs whose constraints and objective functions depend on the

Externí odkaz: https://doaj.org/article/1539c988a37243508dfaa62a3539d77e

Connecting Knowledge Compilation Classes and Width Parameters

Autor: Mikaël Monet, Pierre Senellart, Antoine Amarilli, Florent Capelli

Publikováno v: Theory of Computing Systems
Theory of Computing Systems, Springer Verlag, 2020, ⟨10.1007/s00224-019-09930-2⟩
Theory of Computing Systems, 2020, ⟨10.1007/s00224-019-09930-2⟩

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 su

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6bebc2d4718c4ca9009638d09db18245
https://hal.inria.fr/hal-02163749

Knowledge Compilation Languages as Proof Systems

Autor: Florent Capelli

Publikováno v: Lecture Notes in Computer Science ISBN: 9783030242572
SAT
Theory and Applications of Satisfiability Testing – SAT 2019
Theory and Applications of Satisfiability Testing – SAT 2019, Jul 2019, Lisbon, Portugal. pp.90-99, ⟨10.1007/978-3-030-24258-9_6⟩

In this paper, we study proof systems in the sense of Cook-Reckhow for problems that are higher in the polynomial hierarchy than coNP, in particular, #SAT and maxSAT. We start by explaining how the notion of Cook-Reckhow proof systems can be apply to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ce8f9a033f4fa2b7d38d6756fd168dfe
https://doi.org/10.1007/978-3-030-24258-9_6

Enumerating models of DNF faster: breaking the dependency on the formula size

Autor: Yann Strozecki, Florent Capelli

In this article, we study the problem of enumerating the models of DNF formulas. The aim is to provide enumeration algorithms with a delay that depends polynomially on the size of each model and not on the size of the formula, which can be exponentia

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c9b093d8293adb1801877e2cd88ba197
http://arxiv.org/abs/1810.04006

Understanding the complexity of #SAT using knowledge compilation

Autor: Florent Capelli

Publikováno v: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).

Two main techniques have been used so far to solve the #P-hard problem #SAT. The first one, used in practice, is based on an extension of DPLL for model counting called exhaustive DPLL. The second approach, more theoretical, exploits the structure of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6bd34b87172ccad25f19a04b47bf6e03
https://doi.org/10.1109/lics.2017.8005121