University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > How undecidable are HyperLTL and HyperCTL*?

How undecidable are HyperLTL and HyperCTL*?

Add to your list(s) Download to your calendar using vCal

  • UserMarie Fortin, University of Liverpool
  • ClockFriday 04 March 2022, 14:00-15:00
  • HouseFW26.

If you have a question about this talk, please contact Jamie Vicary.


Temporal logics for the specification of information-flow properties are able to express relations between multiple executions of a system. Two of the most important such logics are HyperLTL and HyperCTL*, which generalise LTL and CTL * by trace quantification. It is known that this expressiveness comes at a price, i.e., satisfiability is undecidable for both logics. We settle the exact complexity of these problems, showing that both are in fact highly undecidable: we prove that HyperLTL satisfiability is \Sigma^1_1-complete and HyperCTL* satisfiability is \Sigma^2_1-complete. To prove \Sigma^2_1 membership for HyperCTL*, we prove that every satisfiable HyperCTL* formula has a model that is equinumerous to the continuum, the first upper bound of this kind. We prove this bound to be tight.

This is joint work with Louwe B. Kuijer, Patrick Totzke and Martin Zimmermann.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity