On counting propositional logic and Wagner's hierarchy

DOI10.1016/j.tcs.2023.113928OpenAlexW4377990693MaRDI QIDQ6100184

Paolo Pistone, Ugo Dal Lago, Melissa Antonelli

Publication date: 21 June 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113928

zbMATH Keywords

computational complexitycounting hierarchycounting quantifiersquantified propositional logic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Extensions of MSO and the monadic counting hierarchy
• An analysis of first-order logics of probability
• Lectures on the Curry-Howard isomorphism
• Games against nature
• Probabilistic logic
• The complexity of combinatorial problems with succinct input representation
• Some observations on the connection between counting and recursion
• Parallel computation with threshold functions
• Probabilistic quantifiers and games
• On tape-bounded probabilistic Turing machine acceptors
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A logic for reasoning about time and reliability
• A logic for reasoning about probabilities
• Reduced forms for stochastic sequential machines
• On measure quantifiers in first-order arithmetic
• Uniform labelled calculi for conditional and counterfactual logics
• Probabilistic logic revisited
• Probabilistic Relational Hoare Logics for Computer-Aided Security Proofs
• Proof Analysis
• Suppes-style sequent calculus for probability logic
• Automata Studies. (AM-34)
• A Survey of Lower Bounds for Satisfiability and Related Problems
• Reasoning with time and chance
• Reasoning about knowledge and probability
• Complexity classes defined by counting quantifiers
• A probabilistic extension of intuitionistic logic
• A decisive characterization of BPP
• Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
• A logical characterization of the counting hierarchy
• Computational Complexity
• Approximate counting in bounded arithmetic
• Markov Chains as Random Input Automata
• Maximin automata
• Probabilistic automata
• Probabilistic Turing Machines and Computability
• Maximin sequential-like machines and chains
• Computability by Probabilistic Turing Machines
• The complexity of theorem-proving procedures

This page was built for publication: On counting propositional logic and Wagner's hierarchy