Parameterized complexity of propositional inclusion and independence logic

DOI10.1007/978-3-031-39784-4_17arXiv2105.14887OpenAlexW4386232019MaRDI QIDQ6199587FDOQ6199587

Authors: Yasir Mahmood, Jonni Virtema 

Publication date: 28 February 2024

Published in: Logic, Language, Information, and Computation (Search for Journal in Brave)

Abstract: We give a comprehensive account on the parameterized complexity of model checking and satisfiability of propositional inclusion and independence logic. We discover that for most parameterizations the problems are either in FPT or paraNP-complete.

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

zbMATH Keywords

team semanticsmodel checkingparameterized complexitysatisfiabilitypropositional logic

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• A logical approach to context-specific independence
• Fundamentals of parameterized complexity
• Probabilistic team semantics
• Dependence logic. A new approach to independence friendly logic
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Parametrized complexity theory.
• Complexity results for modal dependence logic
• A logic for arguing about probabilities in measure teams
• Extended modal dependence logic \(\mathcal{EMDL}\)
• Complexity of model checking for modal dependence logic
• Lower bounds for multiplayer noncooperative games of incomplete information
• Title not available (Why is that?)
• Complexity of Propositional Independence and Inclusion Logic
• Complexity of validity for propositional dependence logics
• Complexity of propositional logics in team semantic
• The expressive power of modal logic with inclusion atoms
• Polyteam semantics
• Descriptive complexity of real computation and probabilistic independence logic
• Enumeration complexity of poor man's propositional dependence logic
• On quantified propositional logics and the exponential time hierarchy
• Approximation and dependence via multiteam semantics
• Team semantics for the specification and verification of hyperproperties
• A parameterized view on the complexity of dependence and independence logic
• Parameterised complexity of model checking and satisfiability in propositional dependence logic
• Model checking and validity in propositional and modal inclusion logics

This page was built for publication: Parameterized complexity of propositional inclusion and independence logic

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