3 papers
cs.FL2021
Adaptive Synchronisation of Pushdown Automata
A. R. Balasubramanian, K. S. Thejaswini
We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown autom…
cs.LO2020
A symmetric attractor-decomposition lifting algorithm for parity games
Marcin Jurdziński, Rémi Morvan, Pierre Ohlmann +1
Progress-measure lifting algorithms for solving parity games have the best worst-case asymptotic runtime, but are limited by their asymmetric nature, and known from the work of Cze…
cs.DS2020
The Strahler number of a parity game
Laure Daviaud, Marcin Jurdziński, K. S. Thejaswini
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smalles…