Deciding Hyperproperties Combined with Functional Specifications - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2022

Deciding Hyperproperties Combined with Functional Specifications


We study satisfiability for HyperLTL with a ∀*∃* quantifier prefix, known to be highly undecidable in general. HyperLTL can express system properties that relate multiple traces (so-called hyperproperties), which are often combined with trace properties that specify functional behavior on single traces. Following this conceptual split, we first define several safety and liveness fragments of ∀*∃* HyperLTL, and characterize the complexity of their (often much easier) satisfiability problem. We then add LTL trace properties as functional specifications. Though (highly) undecidable in many cases, this way of combining “simple” HyperLTL and arbitrary LTL also leads to interesting new decidable fragments. This systematic study of ∀*∃* fragments is complemented by a new (incomplete) algorithm for ∀∃*-HyperLTL satisfiability.
Fichier principal
Vignette du fichier
22-lics-deciding-hyperproperties.pdf (834.49 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03833578 , version 1 (20-09-2023)




Raven Beutner, David Carral, Bernd Finkbeiner, Jana Hofmann, Markus Krötzsch. Deciding Hyperproperties Combined with Functional Specifications. LICS 2022 - 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Aug 2022, Haifa, Israel. pp.1-13, ⟨10.1145/3531130.3533369⟩. ⟨lirmm-03833578⟩
51 View
9 Download



Gmail Mastodon Facebook X LinkedIn More