Model checking and validity in propositional and modal inclusion logics

DOI10.4230/LIPICS.MFCS.2017.32MaRDI QIDQ5111246zbMATH OpenOpenAlexFDO

Authors Lauri Hella, Antti Kuusisto, Arne Meier, Jonni Virtema

Publication date 26 May 2020

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6680142 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2196601 (Why is no real title available?)
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Characterizing relative frame definability in team semantics via the universal modality
• Complexity of Propositional Independence and Inclusion Logic
• Complexity of propositional logics in team semantic
• Compositional semantics for a language of imperfect information
• Dependence and independence
• Dependence logic. A new approach to independence friendly logic
• Expressivity and Complexity of Dependence Logic
• Hierarchies in independence and inclusion logic with strict semantics
• Hierarchies in independence logic
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Lower bounds for multiplayer noncooperative games of incomplete information
• Modal inclusion logic: being lax is simpler than being strict
• Model checking and validity in propositional and modal inclusion logics
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of theorem-proving procedures
• The expressive power of modal logic with inclusion atoms

Cited in

(11)

• 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 and validity in propositional and modal inclusion logics
• scientific article; zbMATH DE number 7056228 (Why is no real title available?)

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)