POPL 2025
Sun 19 - Sat 25 January 2025 Denver, Colorado, United States

This program is tentative and subject to change.

Wed 22 Jan 2025 10:40 - 11:00 at Marco Polo - Automata and Temporal Properties

Temporal logics for hyperproperties have recently emerged as an expressive specification technique for relational properties of reactive systems. While the model checking problem for such logics has been widely studied, there is a scarcity of deductive proof systems for temporal hyperproperties. In particular, hyperproperties with an alternation of universal and existential quantification over system executions are rarely supported. In this paper, we focus on the difficult class of hyperproperties of the form $\forall^\exists^\psi$, where $\psi$ is a safety relation. We show that hyperproperties of this class – which includes many hyperliveness properties of interest – can always be approximated by coinductive relations. This enables intuitive proofs by coinduction. Based on this observation, we define HyCo (\textbf{Hy}perproperties, \textbf{Co}inductively), a mechanized framework to reason about temporal hyperproperties within the Coq proof assistant. We detail the construction of HyCo, provide a proof of its soundness, and exemplify its use by applying it to the verification of reactive systems modeled as imperative programs with nondeterminism and I/O.

This program is tentative and subject to change.

Wed 22 Jan

Displayed time zone: Mountain Time (US & Canada) change

10:40 - 12:00
Automata and Temporal PropertiesPOPL at Marco Polo
10:40
20m
Talk
Coinductive Proofs for Temporal Hyperliveness
POPL
Arthur Correnson CISPA Helmholtz Center for Information Security, Bernd Finkbeiner CISPA Helmholtz Center for Information Security
11:00
20m
Talk
Derivative-Guided Symbolic Execution
POPL
Yongwei Yuan Purdue University, Zhe Zhou Purdue University, Julia Belyakova Purdue University, Suresh Jagannathan Purdue University
11:20
20m
Talk
Symbolic Automata: omega-Regularity Modulo Theories
POPL
Margus Veanes Microsoft Research, Thomas Ball Microsoft Research, Gabriel Ebner Microsoft Research, Ekaterina Zhuchko Tallinn University of Technology
11:40
20m
Talk
Translation of Temporal Logic for Efficient Infinite-State Reactive Synthesis
POPL
Philippe Heim CISPA Helmholtz Center for Information Security, Rayna Dimitrova CISPA Helmholtz Center for Information Security
Pre-print