Deciding Hyperproperties Combined with Functional Specifications - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2022

Deciding Hyperproperties Combined with Functional Specifications

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Licence

Identifiants

Citer

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⟩
107 Consultations
46 Téléchargements

Altmetric

Partager

More