Complexity of Model Checking for Modal Dependence Logic

DOI10.1007/978-3-642-27660-6_19zbMath1298.68170OpenAlexW2137379463MaRDI QIDQ2891371

Peter Lohmann, Johannes Ebbing

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_19

zbMATH Keywords

computational complexitymodal logicmodel checkingdependence 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Boolean dependence logic and partially-ordered connectives ⋮ Propositional logics of dependence ⋮ Complexity of Propositional Independence and Inclusion Logic ⋮ The expressive power of modal logic with inclusion atoms ⋮ Parameterized complexity of propositional inclusion and independence logic ⋮ Transition semantics: the dynamics of dependence logic ⋮ Complexity of validity for propositional dependence logics ⋮ Propositional team logics ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Expressivity and Complexity of Dependence Logic ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Generalized modal satisfiability
• The Complexity of Poor Man's Logic
• Model Checking CTL is Almost Always Inherently Sequential
• Complexity Results for Modal Dependence Logic
• Model-theoretic and Computational Properties of Modal Dependence Logic
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Satisfiability problems for propositional calculi
• Model Checking for Modal Intuitionistic Dependence Logic