DROPS

Document

DOI: 10.4230/LIPIcs.TIME.2018.23

Computational Complexity of a Core Fragment of Halpern-Shoham Logic

Authors: Przemyslaw Andrzej Walega

Published in: LIPIcs, Volume 120, 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Abstract

Halpern-Shoham logic (HS) is a highly expressive interval temporal logic but the satisfiability problem of its formulas is undecidable. The main goal in the research area is to introduce fragments of the logic which are of low computational complexity and of expressive power high enough for practical applications. Recently introduced syntactical restrictions imposed on formulas and semantical constraints put on models gave rise to tractable HS fragments for which prototypical real-world applications have already been proposed. One of such fragments is obtained by forbidding diamond modal operators and limiting formulas to the core form, i.e., the Horn form with at most one literal in the antecedent. The fragment was known to be NL-hard and in P but no tight results were known. In the paper we prove its P-completeness in the case where punctual intervals are allowed and the timeline is dense. Importantly, the fragment is not referential, i.e., it does not allow us to express nominals (which label intervals) and satisfaction operators (which enables us to refer to intervals by their labels). We show that by adding nominals and satisfaction operators to the fragment we reach NP-completeness whenever the timeline is dense or the interpretation of modal operators is weakened (excluding the case when punctual intervals are disallowed and the timeline is discrete). Moreover, we prove that in the case of language containing nominals but not satisfaction operators, the fragment is still NP-complete over dense timelines.

Cite as

Przemyslaw Andrzej Walega. Computational Complexity of a Core Fragment of Halpern-Shoham Logic. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{walega:LIPIcs.TIME.2018.23,
  author =	{Walega, Przemyslaw Andrzej},
  title =	{{Computational Complexity of a Core Fragment of Halpern-Shoham Logic}},
  booktitle =	{25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Alechina, Natasha and N{\o}rv\r{a}g, Kjetil and Penczek, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2018.23},
  URN =		{urn:nbn:de:0030-drops-97880},
  doi =		{10.4230/LIPIcs.TIME.2018.23},
  annote =	{Keywords: Temporal Logic, Interval Logic, Computational Complexity, Hybrid Logic}
}

Document

DOI: 10.4230/LIPIcs.TIME.2017.22

On Expressiveness of Halpern-Shoham Logic and its Horn Fragments

Authors: Przemyslaw Andrzej Walega

Published in: LIPIcs, Volume 90, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017)

Abstract

Abstract: Halpern and Shoham's modal logic of time intervals (HS in short) is an elegant and highly influential propositional interval-based logic. Its Horn fragments and their hybrid extensions have been recently intensively studied and successfully applied in real-world use cases. Detailed investigation of their decidability and computational complexity has been conducted, however, there has been significantly less research on their expressive power. In this paper we make a step towards filling this gap. We (1) show what time structures are definable in the language of HS, and (2) determine which HS fragments are capable of expressing: hybrid machinery, i.e., nominals and satisfaction operators, and somewhere, difference, and everywhere modal operators. These results enable us to classify HS Horn fragments according to their expressive power and to gain insight in the interplay between their decidability/computational complexity and expressiveness.

Cite as

Przemyslaw Andrzej Walega. On Expressiveness of Halpern-Shoham Logic and its Horn Fragments. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{walega:LIPIcs.TIME.2017.22,
  author =	{Walega, Przemyslaw Andrzej},
  title =	{{On Expressiveness of Halpern-Shoham Logic and its Horn Fragments}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-052-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{90},
  editor =	{Schewe, Sven and Schneider, Thomas and Wijsen, Jef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017.22},
  URN =		{urn:nbn:de:0030-drops-79307},
  doi =		{10.4230/LIPIcs.TIME.2017.22},
  annote =	{Keywords: Temporal Logic, Interval Logic, Expressiveness, Hybrid Logic}
}

Search Results

Documents authored by Walega, Przemyslaw Andrzej

Computational Complexity of a Core Fragment of Halpern-Shoham Logic

Abstract

Cite as

On Expressiveness of Halpern-Shoham Logic and its Horn Fragments

Abstract

Cite as

Thanks for your feedback!

Could not send message