40 citations · 92 across the 18 of their papers we have counts for
6 papers · 1 filter
Good for Games Automata: From Nondeterminism to Alternation
Udi Boker, Karoliina Lehtinen
A word automaton recognizing a language is good for games (GFG) if its composition with any game with winning condition preserves the game's winner. While all deterministic…
An Operational Guide to Monitorability
Luca Aceto, Antonis Achilleos, Adrian Francalanza +2
Monitorability delineates what properties can be verified at runtime. Although many monitorability definitions exist, few are defined explicitly in terms of the guarantees provided…
Improving the complexity of Parys' recursive algorithm
Karoliina Lehtinen, Sven Schewe, Dominik Wojtczak
Parys has recently proposed a quasi-polynomial version of Zielonka's recursive algorithm for solving parity games. In this brief note we suggest a variation of his algorithm that i…
The Cost of Monitoring Alone
Luca Aceto, Antonis Achilleos, Adrian Francalanza +2
We compare the succinctness of two monitoring systems for properties of infinite traces, namely parallel and regular monitors. Although a parallel monitor can be turned into an equ…
Register Games
Karoliina Lehtinen, Udi Boker
The complexity of parity games is a long standing open problem that saw a major breakthrough in 2017 when two quasi-polynomial algorithms were published. This article presents a th…
Adventures in Monitorability: From Branching to Linear Time and Back Again
Luca Aceto, Antonis Achilleos, Adrian Francalanza +2
This paper establishes a comprehensive theory of runtime monitorability for Hennessy-Milner logic with recursion, a very expressive variant of the modal -calculus. It investigat…