Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals

DOI10.1016/j.apal.2022.103108OpenAlexW3115491709MaRDI QIDQ5918795

Jonni Virtema, Miika Hannula

Publication date: 16 September 2022

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2022.103108

zbMATH Keywords

dependence logicteam semanticsBlum-Shub-Smale machinemetafinite structures

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed points, Nash equilibria, and the existential theory of the reals
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• On definability in dependence logic
• Inclusion dependencies and their interaction with functional dependencies
• Axioms and algorithms for inferences involving probabilistic independence
• Computing over the reals with addition and order
• Metafinite model theory
• Reachability and connectivity queries in constraint databases
• Counting problems over the reals
• Probabilistic team semantics
• Approximation and dependence via multiteam semantics
• Unifying hidden-variable problems from quantum mechanics by logics of dependence and independence
• Facets of distribution identities in probabilistic team semantics
• A logic for arguing about probabilities in measure teams
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Realizability of Graphs and Linkages
• Two logical hierarchies of optimization problems over the real numbers
• Complexity of Some Geometric and Topological Problems
• Logics which capture complexity classes over the reals
• Linear Programming
• Compositional semantics for a language of imperfect information
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Logics with Multiteam Semantics
• Descriptive complexity of real computation and probabilistic independence logic
• The art gallery problem is ∃ ℝ-complete
• Team Logic and Second-Order Logic
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals

This page was built for publication: Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals