5 papers
The Complexity of Second-order HyperLTL
Hadar Frenkel, Gaëtan Regaud, Martin Zimmermann
We determine the complexity of second-order HyperLTL satisfiability, finite-state satisfiability, and model-checking: All three are equivalent to truth in third-order arithmetic. W…
Complexity of Model Checking Second-Order Hyperproperties on Finite Structures
Bernd Finkbeiner, Hadar Frenkel, Tim Rohde
We study the model checking problem of Hyper2LTL over finite structures. Hyper2LTL is a second-order hyperlogic, that extends the well-studied logic HyperLTL by adding quantificati…
An Information-Flow Perspective on Explainability Requirements: Specification and Verification
Bernd Finkbeiner, Hadar Frenkel, Julian Siber
Explainable systems expose information about why certain observed effects are happening to the agents interacting with them. We argue that this constitutes a positive flow of infor…
Synthesis of Temporal Causality
Bernd Finkbeiner, Hadar Frenkel, Niklas Metzger +1
We present an automata-based algorithm to synthesize omega-regular causes for omega-regular effects on executions of a reactive system, such as counterexamples uncovered by a model…
Monitoring Second-Order Hyperproperties
Raven Beutner, Bernd Finkbeiner, Hadar Frenkel +1
Hyperproperties express the relationship between multiple executions of a system. This is needed in many AI-related fields, such as knowledge representation and planning, to captur…