3 marzo 2023: Melissa Antonelli: On Classical Counting Propositional Logic
Melissa Antonelli (University of Bologna - INRIA)
On Classical Counting Propositional Logic
3 marzo 2023: Piattaforma Zoom, ore 14:00-16:00 (Milan time).
In order to obtain the link for the webinar, please write to: logic.unimi@gmail.com
Abstract:
Interactions between logic and theoretical computer science are several and deep, and the development of deterministic computational models has considerably benefitted from their study. Strikingly, randomized computation was only marginally touched by such fruitful interchanges. Our project precisely aims to start bridging this gap by developing inherently quantitative logics and investigating their relations with specific aspects of probabilistic computation. In this talk, I will deal with the connection between quantitative logics and counting complexity. First, I will introduce the counting propositional logic CPL, the language of which extends that of PL with counting quantifiers, expressing that a formula is true in a certain portion of its possible interpretations. Then, I will show that the complexity of the decision problem for (a special prenex form of) counting formulas perfectly matches the appropriate level of Wagner’s hierarchy, and so CPL provides a probabilistic generalization of the standard purely logical characterization of the polynomial hierarchy via QPL. In the second part of the talk, I will focus on the univariate fragment CPL0 trying to make its connection with stochastic experiments explicit. To do so, I will prove that any (and only) event(s) associated with dyadic distributions can be simulated in this formalism, and present an effective procedure to measure the probability of counting formulas. All the results that I am going to introduce are part of a joint work with Ugo Dal Lago and Paolo Pistone.
La conferenza si terrà in inglese.
La partecipazione alla conferenza è fortemente consigliata agli allievi della Scuola di Dottorato in Filosofia e Scienze dell’Uomo e della Scuola di Dottorato di Mente, Cervello e Ragionamento.
La partecipazione è aperta a tutti gli interessati.