Parameterized complexity of propositional inclusion and independence logic

DOI10.1007/978-3-031-39784-4_17MaRDI QIDQ6199587zbMATH OpenOpenAlexFDO

Authors Yasir Mahmood, Jonni Virtema

Publication date 28 February 2024

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

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)

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.

Cites work

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

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)