activity
20082018
most citedSuccinct progress measures for solving parity games

56 citations · 307 across the 14 of their papers we have counts for

collaborators

15 papers

cs.FL2018★ 19 cited

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…

cs.FL2018

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…

cs.GT2017★ 13 cited

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…

cs.DS2017★ 56 cited

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…

cs.GT2016

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…

cs.GT2015★ 21 cited

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…

cs.GT2015★ 42 cited

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…

cs.LO2014★ 52 cited

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…

cs.GT2014★ 4 cited

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…

cs.FL2013★ 27 cited

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…

cs.GT2009★ 13 cited

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…

cs.GT2009

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…

cs.CC2009★ 29 cited

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…

cs.LO2008★ 28 cited

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…

cs.LO2008★ 3 cited

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…