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

Bérard, Béatrice ; Haar, Stefan ; Hélouët, Loic

Hyper Partial Order Logic

pdf-format:
LIPIcs-FSTTCS-2018-20.pdf (0.5 MB)

Abstract

We define HyPOL, a local hyper logic for partial order models, expressing properties of sets of runs. These properties depict shapes of causal dependencies in sets of partially ordered executions, with similarity relations defined as isomorphisms of past observations. Unsurprisingly, since comparison of projections are included, satisfiability of this logic is undecidable. We then address model checking of HyPOL and show that, already for safe Petri nets, the problem is undecidable. Fortunately, sensible restrictions of observations and nets allow us to bring back model checking of HyPOL to a decidable problem, namely model checking of MSO on graphs of bounded treewidth.

BibTeX - Entry

@InProceedings{brard_et_al:LIPIcs:2018:9919,
  author =	{B{\'e}atrice B{\'e}rard and Stefan Haar and Loic H{\'e}lou{\"e}t},
  title =	{{Hyper Partial Order Logic}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9919},
  URN =		{urn:nbn:de:0030-drops-99190},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.20},
  annote =	{Keywords: Partial orders, logic, hyper-logic}
}

Keywords: Partial orders, logic, hyper-logic
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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