License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10061.3
URN: urn:nbn:de:0030-drops-25240
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2524/
Go to the corresponding Portal

Lohmann, Peter ; Vollmer, Heribert

Complexity Results for Modal Dependence Logic

pdf-format:
10061.LohmannPeter.Paper.2524.pdf (0.3 MB)

Abstract

Modal dependence logic was introduced very recently by Väänänen. It
enhances the basic modal language by an operator dep. For propositional
variables p_1,...,p_n, dep(p_1,...,p_(n-1);p_n) intuitively states that
the value of p_n only depends on those of p_1,...,p_(n-1). Sevenster (J.
Logic and Computation, 2009) showed that satisfiability for modal
dependence logic is complete for nondeterministic exponential time.

In this paper we consider fragments of modal dependence logic obtained
by restricting the set of allowed propositional connectives. We show
that satisfibility for poor man's dependence logic, the language
consisting of formulas built from literals and dependence atoms using
conjunction, necessity and possibility (i.e., disallowing disjunction),
remains NEXPTIME-complete. If we only allow monotone formulas (without
negation, but with disjunction), the complexity drops to
PSPACE-completeness. We also extend Väänänen's language by allowing
classical disjunction besides dependence disjunction and show that the
satisfiability problem remains NEXPTIME-complete. If we then disallow
both negation and dependence disjunction, satistiability is complete for
the second level of the polynomial hierarchy.

In this way we completely classify the computational complexity of the
satisfiability problem for all restrictions of propositional and
dependence operators considered by Väänänen and Sevenster.

BibTeX - Entry

@InProceedings{lohmann_et_al:DagSemProc.10061.3,
  author =	{Lohmann, Peter and Vollmer, Heribert},
  title =	{{Complexity Results for Modal Dependence Logic}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10061},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2524},
  URN =		{urn:nbn:de:0030-drops-25240},
  doi =		{10.4230/DagSemProc.10061.3},
  annote =	{Keywords: Dependence logic, satisfiability problem, computational complexity, poor man's logic}
}

Keywords: Dependence logic, satisfiability problem, computational complexity, poor man's logic
Collection: 10061 - Circuits, Logic, and Games
Issue Date: 2010
Date of publication: 26.04.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI