Decidability of predicate logics with team semantics

DOI10.4230/LIPICS.MFCS.2016.60MaRDI QIDQ4608623zbMATH OpenOpenAlexFDO

Authors Juha Kontinen, Antti Kuusisto, Jonni Virtema

Publication date 21 March 2018

Full work available at URL https://arxiv.org/abs/1410.5037

zbMATH Keywords

complexitydependence logicteam semanticstwo-variable logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Other nonclassical logic (03B60) Complexity of computation (including implicit computational complexity) (03D15)

Abstract: We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIME-complete. Furthermore, we show that the validity problem of two-variable dependence logic is undecidable, thereby solving an open problem from the team semantics literature. We also briefly analyse the complexity of the Bernays-Sch"onfinkel-Ramsey prefix classes of dependence logic.

Recommendations

• Complexity of propositional logics in team semantic
• On the complexity of team logic and its two-variable fragment
• Complexity thresholds in inclusion logic
• Complexity of two-variable dependence logic and IF-logic
• Tractability frontier of data complexity in team semantics

Cited in

(25)

• Approximation and dependence via multiteam semantics
• Doubly strongly first order dependencies
• On definability of team relations with \(k\)-invariant atoms
• Embedding causal team languages into predicate logic
• Enumerating teams in first-order team logics
• scientific article; zbMATH DE number 7447734 (Why is no real title available?)
• Complexity of propositional logics in team semantic
• Complexity of two-variable dependence logic and IF-logic
• On the complexity of team logic and its two-variable fragment
• Tractability frontier of data complexity in team semantics
• On quantified propositional logics and the exponential time hierarchy
• Characterizing strongly first order dependencies: the non-jumping relativizable case
• Tractability Frontier of Data Complexity in Team Semantics
• Counting of Teams in First-Order Team Logics
• scientific article; zbMATH DE number 7407786 (Why is no real title available?)
• Characterizing downwards closed, strongly first-order, relativizable dependencies
• Expressivity and Complexity of Dependence Logic
• Propositional team logics
• A Van Benthem Theorem for Modal Team Semantics
• Complexity thresholds in inclusion logic
• COMPLETE LOGICS FOR ELEMENTARY TEAM PROPERTIES
• Strongly first order, domain independent dependencies: the union-closed case
• Counting of teams in first-order team logics
• Strongly first order disjunctive embedded dependencies in team semantics
• Doubly strongly first-order dependencies

This page was built for publication: Decidability of predicate logics with team semantics

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