Realizable and Context-Free Hyperlanguages

Hadar Frenkel
(CISPA Helmholtz Center for Information Security, Saarbrücken, Germany )
Sarai Sheinvald
(Department of Software Engineering, Braude College of Engineering, Karmiel, Israel)

Hyperproperties lift conventional trace-based languages from a set of execution traces to a set of sets of executions. From a formal-language perspective, these are sets of sets of words, namely hyperlanguages. Hyperautomata are based on classical automata models that are lifted to handle hyperlanguages. Finite hyperautomata (NFH) have been suggested to express regular hyperproperties. We study the realizability problem for regular hyperlanguages: given a set of languages, can it be precisely described by an NFH? We show that the problem is complex already for singleton hyperlanguages. We then go beyond regular hyperlanguages, and study context-free hyperlanguages. We show that the natural extension to context-free hypergrammars is highly undecidable. We then suggest a refined model, namely synchronous hypergrammars, which enables describing interesting non-regular hyperproperties, while retaining many decidable properties of context-free grammars.

In Pierre Ganty and Dario Della Monica: Proceedings of the 13th International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2022), Madrid, Spain, September 21-23, 2022, Electronic Proceedings in Theoretical Computer Science 370, pp. 114–130.
Published: 20th September 2022.

ArXived at: https://dx.doi.org/10.4204/EPTCS.370.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org