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.TIME.2018.16
URN: urn:nbn:de:0030-drops-97816
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9781/
Go to the corresponding LIPIcs Volume Portal

Kernberger, Daniel ; Lange, Martin

On the Expressive Power of Hybrid Branching-Time Logics

pdf-format:
LIPIcs-TIME-2018-16.pdf (0.5 MB)

Abstract

Hybrid branching-time logics are a powerful extension of branching-time logics like CTL, CTL^* or even the modal mu-calculus through the addition of binders, jumps and variable tests. Their expressiveness is not restricted by bisimulation-invariance anymore. Hence, they do not retain the tree model property, and the finite model property is equally lost. Their satisfiability problems are typically undecidable, their model checking problems (on finite models) are decidable with complexities ranging from polynomial to non-elementary time. In this paper we study the expressive power of such hybrid branching-time logics beyond some earlier results about their invariance under hybrid bisimulations. In particular, we aim to extend the hierarchy of non-hybrid branching-time logics CTL, CTL^+, CTL^* and the modal mu-calculus to their hybrid extensions. We show that most separation results can be transferred to the hybrid world, even though the required techniques become a bit more involved. We also present some collapse results for restricted classes of models that are especially worth investigating, namely linear, tree-shaped and finite models.

BibTeX - Entry

@InProceedings{kernberger_et_al:LIPIcs:2018:9781,
  author =	{Daniel Kernberger and Martin Lange},
  title =	{{On the Expressive Power of Hybrid Branching-Time Logics}},
  booktitle =	{25th International Symposium on Temporal Representation  and Reasoning (TIME 2018)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9781},
  URN =		{urn:nbn:de:0030-drops-97816},
  doi =		{10.4230/LIPIcs.TIME.2018.16},
  annote =	{Keywords: branching-time, mu-calculus, hybrid logics, expressiveness}
}

Keywords: branching-time, mu-calculus, hybrid logics, expressiveness
Collection: 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)
Issue Date: 2018
Date of publication: 08.10.2018

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