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

Deciding Hyperproperties Combined with Functional Specifications

Abstract

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)

Licence

Identifiers

Cite

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⟩
73 View
11 Download

Altmetric

Share

More