On counting propositional logic and Wagner's hierarchy

DOI10.1016/J.TCS.2023.113928MaRDI QIDQ6100184zbMATH OpenOpenAlexFDO

Authors Melissa Antonelli, Ugo Dal Lago, Paolo Pistone

Publication date 21 June 2023

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

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• A logical characterization of the counting hierarchy
• Complexity classes defined by counting quantifiers
• Descriptive complexity for counting complexity classes
• On the expressive power of counting
• Descriptive complexity for counting complexity classes

Cites work

• A decisive characterization of BPP
• A logic for reasoning about probabilities
• A logic for reasoning about time and reliability
• A logical characterization of the counting hierarchy
• A probabilistic extension of intuitionistic logic
• A survey of lower bounds for satisfiability and related problems.
• An analysis of first-order logics of probability
• Approximate counting in bounded arithmetic
• Automata Studies. (AM-34)
• Complete sets and the polynomial-time hierarchy
• Complexity classes defined by counting quantifiers
• Computability by Probabilistic Turing Machines
• Computational Complexity
• Extensions of MSO and the monadic counting hierarchy
• Games against nature
• scientific article; zbMATH DE number 3883612 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3557236 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 2046116 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• Lectures on the Curry-Howard isomorphism
• Markov Chains as Random Input Automata
• Maximin automata
• Maximin sequential-like machines and chains
• On measure quantifiers in first-order arithmetic
• On tape-bounded probabilistic Turing machine acceptors
• Parallel computation with threshold functions
• Probabilistic automata
• Probabilistic logic
• Probabilistic logic revisited
• Probabilistic logics based on Riesz spaces
• Probabilistic quantifiers and games
• Probabilistic relational Hoare logics for computer-aided security proofs
• Probabilistic Turing Machines and Computability
• Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
• Proof Analysis
• Reasoning about knowledge and probability
• Reasoning with time and chance
• Reduced forms for stochastic sequential machines
• Some observations on the connection between counting and recursion
• Suppes-style sequent calculus for probability logic
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The complexity of theorem-proving procedures
• The polynomial-time hierarchy
• The sub-additives: a proof theory for probabilistic choice extending linear logic
• Uniform labelled calculi for conditional and counterfactual logics

Cited in

(3)

• A logical characterization of the counting hierarchy
• Towards logical foundations for probabilistic computation
• Curry and Howard meet Borel

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6100184)