We introduce an extension of classical propositional logic with counting quantifiers. These forms of quantification make it possible to express that a formula is true in a certain portion of the set of all its interpretations. Beyond providing a sound and complete proof system for this logic, we show that validity problems for counting propositional logic can be used to capture counting complexity classes. More precisely, we show that the complexity of the decision problems for validity of prenex formulas of this logic perfectly match the appropriate levels of Wagner's counting hierarchy.

Antonelli, M., Dal Lago, U., Pistone, P. (2023). On Counting Propositional Logic and Wagner's Hierarchy. THEORETICAL COMPUTER SCIENCE, 966–967, 1-34 [10.1016/j.tcs.2023.113928].

On Counting Propositional Logic and Wagner's Hierarchy

Antonelli, Melissa;Dal Lago, Ugo;Pistone, Paolo
2023

Abstract

We introduce an extension of classical propositional logic with counting quantifiers. These forms of quantification make it possible to express that a formula is true in a certain portion of the set of all its interpretations. Beyond providing a sound and complete proof system for this logic, we show that validity problems for counting propositional logic can be used to capture counting complexity classes. More precisely, we show that the complexity of the decision problems for validity of prenex formulas of this logic perfectly match the appropriate levels of Wagner's counting hierarchy.
2023
Antonelli, M., Dal Lago, U., Pistone, P. (2023). On Counting Propositional Logic and Wagner's Hierarchy. THEORETICAL COMPUTER SCIENCE, 966–967, 1-34 [10.1016/j.tcs.2023.113928].
Antonelli, Melissa; Dal Lago, Ugo; Pistone, Paolo
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397523002414-main.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 559.47 kB
Formato Adobe PDF
559.47 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/928633
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact