Model Checking and Validity in Propositional and Modal Inclusion Logics

Propositional and modal inclusion logic are formalisms that belong to the family of logics based on team semantics. This article investigates the model checking and validity problems of these logics. We identify complexity bounds for both problems, covering both lax and strict team semantics. By doing so, we come close to finalizing the programme that aims to completely classify the complexities of the basic reasoning problems for modal and propositional dependence, independence and inclusion logics.

• Publication year

  2016

• Venue

  International Symposium on Mathematical Foundations of Computer Science

• Publication date

  2016-09-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.MFCS.2017.32arXiv 1609.06951
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Bio-inspired synthesis of xishacorenes A, B, and C, and a new congener from fuscol

  2019cited by this paper
• Complexity of Propositional Logics in Team Semantic

  2018influential reference
• Canonical Models and the Complexity of Modal Team Logic

  2017cited by this paper
• Inclusion dependencies and their interaction with functional dependencies in SQL

  2017cited by this paper
• Polyteam Semantics

  2017cited by this paper
• Team Semantics for the Specification and Verification of Hyperproperties

  2017cited by this paper
• Computers And Intractability A Guide To The Theory Of Np Completeness

  2016cited by this paper
• Characterizing Relative Frame Definability in Team Semantics via the Universal Modality

  2016cited by this paper
• Expressivity and Complexity of Dependence Logic

  2016cited by this paper
• Propositional team logics

  2016influential reference
• Axiomatizations of Team Logics

  2016cited by this paper
• Validity and Entailment in Modal and Propositional Dependence Logics

  2016influential reference
• Characterizing Frame Definability in Team Semantics via the Universal Modality

  2015cited by this paper
• Complexity of Propositional Logics in Team Semantics

  2015cited by this paper
• Complexity of Propositional Independence and Inclusion Logic

  2015influential reference
• Approximation and dependence via multiteam semantics

  2015cited by this paper
• Modal Inclusion Logic: Being Lax is Simpler than Being Strict

  2015cited by this paper
• The expressive power of modal logic with inclusion atoms

  2015cited by this paper
• Satisfiability and model checking in team based logics

  2014influential reference
• Axiomatizing Propositional Dependence Logics

  2014cited by this paper
• Complexity of validity for propositional dependence logics

  2014cited by this paper
• Hierarchies in independence and inclusion logic with strict semantics

  2014cited by this paper
• The Expressive Power of Modal Dependence Logic

  2014cited by this paper
• Modal Independence Logic

  2014influential reference
• Inclusion Logic and Fixed Point Logic

  2013cited by this paper
• Hierarchies in independence logic

  2013cited by this paper
• Extended Modal Dependence Logic

  2013cited by this paper
• On Dependence Logic

  2013influential reference
• A Finite Axiomatization of Conditional Independence and Inclusion Dependencies

  2013cited by this paper
• Dependence and Independence

  2012influential reference
• Inclusion and exclusion dependencies in team semantics - On some logics of imperfect information

  2011cited by this paper
• Complexity of Model Checking for Modal Dependence Logic

  2011cited by this paper
• Complexity Results for Modal Dependence Logic

  2010cited by this paper
• Introduction to Circuit Complexity: A Uniform Approach

  2010cited by this paper
• Model-theoretic and Computational Properties of Modal Dependence Logic

  2009influential reference
• Modal Dependence Logic

  2008cited by this paper
• The Complexity of Temporal Logic Model Checking

  2002cited by this paper
• Modal Logic

  2001cited by this paper
• Incomplete Information

  2000cited by this paper
• Introduction to Circuit Complexity

  1999cited by this paper
• Compositional Semantics for a Language of Imperfect Information

  1997cited by this paper
• The Boolean formula value problem is in ALOGTIME

  1987cited by this paper
• Automatic verification of finite-state concurrent systems using temporal logic specifications

  1986cited by this paper
• Relational queries computable in polynomial time (Extended Abstract)

  1982cited by this paper
• Inclusion dependencies and their interaction with functional dependencies

  1982cited by this paper
• The complexity of relational query languages (Extended Abstract)

  1982cited by this paper
• Proceedings of the fourteenth annual ACM symposium on Theory of computing

  1982cited by this paper
• The Computational Complexity of Provability in Systems of Modal Propositional Logic

  1977cited by this paper
• The monotone and planar circuit value problems are log space complete for P

  1977cited by this paper
• Word problems requiring exponential time(Preliminary Report)

  1973cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper

• Complexity Results in Team Semantics: Nonemptiness Is Not So Complex

  2025influential citation
• Axiomatizing modal inclusion logic and its variants

  2023cites this paper
• Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity

  2023cites this paper
• Parameterized complexity of weighted team definability

  2023cites this paper
• Parameterised Complexity of Propositional Logic in Team Semantics

  2021cites this paper
• Parameterized Complexity of Propositional Inclusion and Independence Logic

  2021cites this paper
• Team logic: axioms, expressiveness, complexity

  2020influential citation
• Enumerating Teams in First-Order Team Logics

  2020cites this paper
• Propositional union closed team logics

  2020cites this paper
• Linear-time Temporal Logic with Team Semantics: Expressivity and Complexity

  2020cites this paper
• Parameterised complexity of model checking and satisfiability in propositional dependence logic

  2019cites this paper
• Arity Fragments of Logics with Team Semantics

  2018cites this paper
• Complexity of Propositional Logics in Team Semantic

  2018cites this paper
• Enumeration Complexity of Poor Man's Propositional Dependence Logic

  2017cites this paper
• Team Semantics for the Specification and Verification of Hyperproperties

  2017cites this paper
• Canonical Models and the Complexity of Modal Team Logic

  2017cites this paper
• The Expressive Power of k-ary Exclusion Logic

  2016cites this paper
• Validity and Entailment in Modal and Propositional Dependence Logics

  2016influential citation
• The Entailment Problem in Modal and Propositional Dependence Logics

  2016cites this paper
• Approximation and dependence via multiteam semantics

  2015cites this paper
• Complexity of Propositional Logics in Team Semantics

  2015influential citation
• Satisfiability of Modal Inclusion Logic

  2015cites this paper