License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.28
URN: urn:nbn:de:0030-drops-76691
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7669/
Go to the corresponding LIPIcs Volume Portal

Hannula, Miika

Validity and Entailment in Modal and Propositional Dependence Logics

pdf-format:
LIPIcs-CSL-2017-28.pdf (0.6 MB)

Abstract

The computational properties of modal and propositional dependence logics have been extensively studied over the past few years, starting from a result by Sevenster showing NEXPTIME-completeness of the satisfiability problem for modal dependence logic. Thus far, however, the validity and entailment properties of these logics have remained uncharacterised to a great extent. This paper establishes a complete classification of the complexity of validity and entailment in modal and propositional dependence logics. In particular, we address the question of the complexity of validity in modal dependence logic. By showing that it is NEXPTIME-complete we refute an earlier conjecture proposing a higher complexity for the problem.

BibTeX - Entry

@InProceedings{hannula:LIPIcs:2017:7669,
  author =	{Miika Hannula},
  title =	{{Validity and Entailment in Modal and Propositional Dependence Logics}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7669},
  URN =		{urn:nbn:de:0030-drops-76691},
  doi =		{10.4230/LIPIcs.CSL.2017.28},
  annote =	{Keywords: modal logic, propositional logic, dependence logic, entailment, validity, complexity}
}

Keywords: modal logic, propositional logic, dependence logic, entailment, validity, complexity
Collection: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 16.08.2017

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