We introduce and study counting propositional logic, an extension of propositional logic with counting quantifiers. This new kind of quantification makes it possible to express that the argument formula is true in a certain portion of all possible interpretations. We show that this logic, beyond admitting a satisfactory proof-theoretical treatment, can be related to computational complexity: the complexity of the underlying decision problem perfectly matches the appropriate level of Wagner's counting hierarchy.
On Counting Propositional Logic and Wagner's Hierarchy / Antonelli M.; Dal Lago U.; Pistone P.. - ELETTRONICO. - 3072:(2021), pp. 107-121. (Intervento presentato al convegno 22nd Italian Conference on Theoretical Computer Science, ICTCS 2021 tenutosi a ita nel 2021).
On Counting Propositional Logic and Wagner's Hierarchy
Antonelli M.
;Dal Lago U.
;Pistone P.
2021
Abstract
We introduce and study counting propositional logic, an extension of propositional logic with counting quantifiers. This new kind of quantification makes it possible to express that the argument formula is true in a certain portion of all possible interpretations. We show that this logic, beyond admitting a satisfactory proof-theoretical treatment, can be related to computational complexity: the complexity of the underlying decision problem perfectly matches the appropriate level of Wagner's counting hierarchy.| File | Dimensione | Formato | |
|---|---|---|---|
|
ictcs2021.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
743.82 kB
Formato
Adobe PDF
|
743.82 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
