Parameterised complexity of model checking and satisfiability in propositional dependence logic

DOI10.1007/s10472-021-09730-wOpenAlexW4241215655MaRDI QIDQ5918486

Yasir Mahmood, Arne Meier

Publication date: 14 February 2022

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

model checkingsatisfiabilitypropositional dependence logicparameterised complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70)

Related Items (1)

Parameterized complexity of propositional inclusion and independence logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structural tractability of counting of solutions to conjunctive queries
• Propositional logics of dependence
• Fundamentals of parameterized complexity
• Model-checking games for logics of imperfect information
• Complexity of validity for propositional dependence logics
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Backdoors into heterogeneous classes of SAT and CSP
• Graph minors. V. Excluding a planar graph
• Armstrong databases for functional and inclusion dependencies
• Probabilistic team semantics
• Enumeration complexity of poor man's propositional dependence logic
• Polyteam semantics
• Augmenting tractable fragments of abstract argumentation
• Approximation and dependence via multiteam semantics
• Complexity results for modal dependence logic
• Algorithms for propositional model counting
• Backdoors to planning
• Backdoors to tractable answer set programming
• Parametrized complexity theory.
• Dependence Logic
• Strong Backdoors for Default Logic
• The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space
• Complexity of Model Checking for Modal Dependence Logic
• Modal independence logic:
• Complexity of Finding Embeddings in a k-Tree
• On the Structure of Armstrong Relations for Functional Dependencies
• Complexity of Propositional Logics in Team Semantic
• Backdoors for Linear Temporal Logic
• Towards a Logic of Information Exchange
• Team semantics for the specification and verification of hyperproperties
• When is the evaluation of conjunctive queries tractable?
• Model checking and validity in propositional and modal inclusion logics
• Backdoors to Normality for Disjunctive Logic Programs
• Parametrised Complexity of Satisfiability in Temporal Logic
• Parameterized Algorithms
• The complexity of theorem-proving procedures
• A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
• Parameterised complexity of model checking and satisfiability in propositional dependence logic

This page was built for publication: Parameterised complexity of model checking and satisfiability in propositional dependence logic