Knowledge compilation languages as proof systems

Capelli, Florent

Document type :

Pré-publication ou Document de travail

Title :

Knowledge compilation languages as proof systems

Author(s) :

Capelli, Florent [Auteur]

Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]

HAL domain(s) :

Informatique [cs]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Collections :

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

Source :

Harvested from HAL

Files

http://arxiv.org/pdf/1903.04039
Open access
Access the document

1903.04039
Open access
Access the document

Knowledge compilation languages as proof systems BibTeX CSV Excel RIS

Files

Knowledge compilation languages as proof systems

BibTeX

CSV

Excel

RIS