Complexity Results for Modal Dependence Logic

Authors Peter Lohmann, Heribert Vollmer



PDF
Thumbnail PDF

File

DagSemProc.10061.3.pdf
  • Filesize: 269 kB
  • 15 pages

Document Identifiers

Author Details

Peter Lohmann
Heribert Vollmer

Cite AsGet BibTex

Peter Lohmann and Heribert Vollmer. Complexity Results for Modal Dependence Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.10061.3

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.
Keywords
  • Dependence logic
  • satisfiability problem
  • computational complexity
  • poor man's logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail