56 citations · 307 across the 14 of their papers we have counts for
15 papers
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow +3
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and St…
When is Containment Decidable for Probabilistic Automata?
Laure Daviaud, Marcin Jurdziński, Ranko Lazić +3
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean au…
Perfect Half Space Games
Thomas Colcombet, Marcin Jurdziński, Ranko Lazić +1
We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional weights diverge in a direction which is consistent with a…
Succinct progress measures for solving parity games
Marcin Jurdzinski, Ranko Lazic
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly sub…
Mean-Payoff Games on Timed Automata
Shibashis Guha, Marcin Jurdzinski, Krishna S. +1
Mean-payoff games on timed automata are played on the infinite weighted graph of configurations of priced timed automata between two players, Player Min and Player Max, by moving a…
Distributed Methods for Computing Approximate Equilibria
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis +3
We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same t…
Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time
Marcin Jurdziński, Ranko Lazić, Sylvain Schmitz
We generalise the hyperplane separation technique (Chatterjee and Velner, 2013) from multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the latter…
Stochastic Timed Automata
Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye +4
A stochastic timed automaton is a purely stochastic process defined on a timed automaton, in which both delays and discrete choices are made randomly. We study the almost-sure mode…
Approximate well-supported Nash equilibria in symmetric bimatrix games
Artur Czumaj, Michail Fasoulakis, Marcin Jurdziński
The -well-supported Nash equilibrium is a strong notion of approximation of a Nash equilibrium, where no player has an incentive greater than to deviate…
Reachability in Two-Clock Timed Automata is PSPACE-complete
John Fearnley, Marcin Jurdziński
A recent result of Haase et al. has shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reacha…
Average-Time Games on Timed Automata
Marcin Jurdzinski, Ashutosh Trivedi
An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taki…
Linear Complementarity Algorithms for Infinite Games
John Fearnley, Marcin Jurdziński, Rahul Savani
The performance of two pivoting algorithms, due to Lemke and Cottle and Dantzig, is studied on linear complementarity problems (LCPs) that arise from infinite games, such as parity…
Reachability-time games on timed automata
Marcin Jurdziński, Ashutosh Trivedi
In a reachability-time game, players Min and Max choose moves so that the time to reach a final state in a timed automaton is minimised or maximised, respectively. Asarin and Maler…
Model Checking Probabilistic Timed Automata with One or Two Clocks
Marcin Jurdzinski, Francois Laroussinie, Jeremy Sproston
Probabilistic timed automata are an extension of timed automata with discrete probability distributions. We consider model-checking algorithms for the subclasses of probabilistic t…
Alternating Automata on Data Trees and XPath Satisfiability
Marcin Jurdzinski, Ranko Lazic
A data tree is an unranked ordered tree whose every node is labelled by a letter from a finite alphabet and an element ("datum") from an infinite set, where the latter can only be…