Model checking and validity in propositional and modal inclusion logics

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

Authors: Lauri Hella, Antti Kuusisto, Arne Meier, 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

Recommendations

• Model checking and validity in propositional and modal inclusion logics
• Complexity of validity for propositional dependence logics
• scientific article; zbMATH DE number 7056228
• Complexity of propositional logics in team semantic
• Complexity thresholds in inclusion logic

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
• Dependence logic. A new approach to independence friendly logic
• 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?)
• Characterizing frame definability in team semantics 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 (12)

• Modal inclusion logic: being lax is simpler than being strict
• Satisfiability of modal inclusion logic. Lax and strict semantics
• Model checking and validity in propositional and modal inclusion logics
• The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions
• Propositional union closed team logics
• Canonical models and the complexity of modal team logic
• The expressive power of \(k\)-ary exclusion logic
• Complexity thresholds in inclusion logic
• Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption
• Model checking existential logic on partially ordered sets
• Model checking and validity in propositional and modal inclusion logics
• Title not available (Why is that?)

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)