HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Knowledge compilation languages as proof systems

Florent Capelli 1, 2
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : 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 these problems and show how one can twist existing languages in knowledge compilation such as decision DNNF so that they can be seen as proof systems for problems such as #SAT and maxSAT.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Contributor : Florent Capelli Connect in order to contact the contributor
Submitted on : Monday, June 24, 2019 - 3:32:49 PM
Last modification on : Thursday, March 24, 2022 - 3:43:00 AM

Links full text


  • HAL Id : hal-02163761, version 1
  • ARXIV : 1903.04039


Florent Capelli. Knowledge compilation languages as proof systems. 2019. ⟨hal-02163761⟩



Record views