Model Checking and Validity in Propositional and Modal Inclusion Logics

DOI10.4230/LIPICS.MFCS.2017.32zbMATH Open1441.68132arXiv1609.06951OpenAlexW3093094759MaRDI QIDQ5111246FDOQ5111246

Arne Meier, Antti Kuusisto, Lauri Hella, Jonni Virtema

Publication date: 26 May 2020

Abstract: 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 finalising the programme that ultimately aims to classify the complexities of the central reasoning problems for modal and propositional dependence, independence, and inclusion logics.

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

zbMATH Keywords

complexitymodel checkinginclusion logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Specification and verification (program logics, model checking, etc.) (68Q60) Logic in computer science (03B70)

Cites Work

• Dependence and independence
• Title not available (Why is that?)
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Title not available (Why is that?)
• Compositional semantics for a language of imperfect information
• The complexity of theorem-proving procedures
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Lower bounds for multiplayer noncooperative games of incomplete information
• Hierarchies in independence logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Title not available (Why is that?)
• Characterising modal definability of team-based logics via the universal modality
• Complexity of Propositional Independence and Inclusion Logic
• Complexity of Propositional Logics in Team Semantic
• The expressive power of modal logic with inclusion atoms
• Hierarchies in independence and inclusion logic with strict semantics
• Expressivity and Complexity of Dependence Logic
• Model Checking and Validity in Propositional and Modal Inclusion Logics
• Characterizing Relative Frame Definability in Team Semantics via the Universal Modality
• Modal Inclusion Logic: Being Lax is Simpler than Being Strict

Cited In (8)

• The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions
• Propositional union closed team logics
• The expressive power of \(k\)-ary exclusion logic
• Model Checking and Validity in Propositional and Modal Inclusion Logics
• Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption
• Model checking existential logic on partially ordered sets
• Title not available (Why is that?)
• Canonical Models and the Complexity of Modal Team Logic

This page was built for publication: Model Checking and Validity in Propositional and Modal Inclusion Logics

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