Stochastic Timed Automata

Autor: Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Quentin Menet, Christel Baier, Marcus Groesser, Marcin Jurdzinski

Publikováno v: Logical Methods in Computer Science, Vol Volume 10, Issue 4 (2014)

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 model-checking problem for this model, that is, given a stochastic timed a

Externí odkaz: https://doaj.org/article/f92695f2a20e4670973631558ddb9c08

Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games

Autor: Ranko Lazić, Paweł Parys, Marcin Jurdziński, Laure Daviaud, Wojciech Czerwiński, Nathanaël Fijalkow

Publikováno v: SODA
SODA, Jan 2019, San Diego, United States

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 Stephan (2017): play summaries, progress measures and register games. We

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2e63c9899da7b6ecbc353108084fbc39
https://hal.archives-ouvertes.fr/hal-02395778

Succinct progress measures for solving parity games

Autor: Marcin Jurdziński, Ranko Lazić

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 subexponential. We devise an alternative quasi-polynomial time algorithm

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4904cff9171b2d0c7beec3f8fc4891bf

Average-price-per-reward games on hybrid automata with strong resets

Autor: Michał Rutkowski, Ranko Lazić, Marcin Jurdziński

Publikováno v: International Journal on Software Tools for Technology Transfer. 13:553-569

We study price-per-reward games on hybrid automata with strong resets. They generalise average-price games previously studied and have applications in scheduling. We obtain decidability results by a translation to a novel class of finite graphs with

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::31b94203053ec1a65d1fb5426825b4aa
https://doi.org/10.1007/s10009-010-0180-8

Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time

Autor: Marcin Jurdziński, Sylvain Schmitz, Ranko Lazić

Publikováno v: Automata, Languages, and Programming ISBN: 9783662476659
ICALP 2015: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming
ICALP 2015: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, Jul 2015, Kyoto, Japan. pp.260--272, ⟨10.1007/978-3-662-47666-6_21⟩

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 whose running time is exponential only in the dimension, but not in th

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9909f0a2095cd0533a6bbd2c5c12cd64