Realizing Omega-regular Hyperproperties

Finkbeiner, Bernd and Hahn, Christopher and Hofmann, Jana and Tentrup, Leander
(2020) Realizing Omega-regular Hyperproperties.
In: Computer Aided Verification - 32nd International Conference, CAV 2020, Los Angeles, CA, USA, July 21-24, 2020, Proceedings, Part II, 21.07.2020 - 24.07.2020, Los Angeles.
Conference: CAV Computer Aided Verification

[img]
Preview
Text
main_cav.pdf - Accepted Version

Download (411kB) | Preview
Official URL: https://doi.org/10.1007/978-3-030-53291-8\_4

Abstract

We study the expressiveness and reactive synthesis problem of HyperQPTL, a logic that specifies omega-regular hyperproperties. HyperQPTL is an extension of linear-time temporal logic (LTL) with explicit trace and propositional quantification and therefore truly combines trace relations and omega-regularity. As such, HyperQPTL can express promptness, which states that there is a common bound on the number of steps up to which an event must have happened. We demonstrate how the HyperQPTL formulation of promptness differs from the type of promptness expressible in the logic Prompt-LTL. Furthermore, we study the realizability problem of HyperQPTL by identifying decidable fragments, where one decidable fragment contains formulas for promptness. We show that, in contrast to the satisfiability problem of HyperQPTL, propositional quantification has an immediate impact on the decidability of the realizability problem. We present a reduction to the realizability problem of HyperLTL, which immediately yields a bounded synthesis procedure. We implemented the synthesis procedure for HyperQPTL in the bounded synthesis tool BoSy. Our experimental results show that a range of arbiter satisfying promptness can be synthesized.

Actions

Actions (login required)

View Item View Item