5 papers
Enumerating Error Bounded Polytime Algorithms Through Arithmetical Theories
Melissa Antonelli, Ugo Dal Lago, Davide Davoli +2
We consider a minimal extension of the language of arithmetic, such that the bounded formulas provably total in a suitably-defined theory à la Buss (expressed in this new language)…
Some Remarks on Counting Propositional Logic
Melissa Antonelli
Counting propositional logic was recently introduced in relation to randomized computation and shown able to logically characterize the full counting hierarchy. In this paper we ai…
Curry and Howard Meet Borel
Melissa Antonelli, Ugo Dal Lago, Paolo Pistone
We show that an intuitionistic version of counting propositional logic corresponds, in the sense of Curry and Howard, to an expressive type system for the probabilistic event lambd…
On Measure Quantifiers in First-Order Arithmetic (Long Version)
Melissa Antonelli, Ugo Dal Lago, Paolo Pistone
We study the logic obtained by endowing the language of first-order arithmetic with second-order measure quantifiers. This new kind of quantification allows us to express that the…
On Counting Propositional Logic
Melissa Antonelli, Ugo Dal Lago, Paolo Pistone
We study counting propositional logic as an extension of propositional logic with counting quantifiers. We prove that the complexity of the underlying decision problem perfectly ma…