License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.27
URN: urn:nbn:de:0030-drops-170905
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17090/
Bozzelli, Laura ;
Peron, Adriano ;
Sánchez, César
Expressiveness and Decidability of Temporal Logics for Asynchronous Hyperproperties
Abstract
Hyperproperties are properties of systems that relate different executions traces, with many applications from security to symmetry, consistency models of concurrency, etc. In recent years, different linear-time logics for specifying asynchronous hyperproperties have been investigated. Though model checking of these logics is undecidable, useful decidable fragments have been identified with applications e.g. for asynchronous security analysis. In this paper, we address expressiveness and decidability issues of temporal logics for asynchronous hyperproperties. We compare the expressiveness of these logics together with the extension S1S[E] of S1S with the equal-level predicate by obtaining an almost complete expressiveness picture. We also study the expressive power of these logics when interpreted on singleton sets of traces. We show that for two asynchronous extensions of HyperLTL, checking the existence of a singleton model is already undecidable, and for one of them, namely Context HyperLTL (HyperLTL_C), we establish a characterization of the singleton models in terms of the extension of standard FO[<] over traces with addition. This last result generalizes the well-known equivalence between FO[<] and LTL. Finally, we identify new boundaries on the decidability of model checking HyperLTL_C.
BibTeX - Entry
@InProceedings{bozzelli_et_al:LIPIcs.CONCUR.2022.27,
author = {Bozzelli, Laura and Peron, Adriano and S\'{a}nchez, C\'{e}sar},
title = {{Expressiveness and Decidability of Temporal Logics for Asynchronous Hyperproperties}},
booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)},
pages = {27:1--27:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-246-4},
ISSN = {1868-8969},
year = {2022},
volume = {243},
editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17090},
URN = {urn:nbn:de:0030-drops-170905},
doi = {10.4230/LIPIcs.CONCUR.2022.27},
annote = {Keywords: Hyperproperties, Asynchronous hyperproperties, Temporal logics for hyperproperties, Expressiveness, Decidability, Model checking}
}
|
Keywords: |
|
Hyperproperties, Asynchronous hyperproperties, Temporal logics for hyperproperties, Expressiveness, Decidability, Model checking |
|
Collection: |
|
33rd International Conference on Concurrency Theory (CONCUR 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
06.09.2022 |
