2021

Daviaud, Laure, Jurdzinski, Marcin, Lazic, Ranko, Mazowiecki, Filip, Pérez, Guillermo A. and Worrell, James (2021) When are emptiness and containment decidable for probabilistic automata? Journal of Computer and System Sciences . doi:10.1016/j.jcss.2021.01.006 (In Press)

2020

Daviaud, Laure, Jurdzinski, Marcin and Thejaswini, K. S. (2020) The Strahler number of a parity game. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020. Published in: Leibniz International Proceedings in Informatics (LIPIcs) 123:1-123:19. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2020.123 (In Press)

2019

Czerwiński, Wojciech, Daviaud, Laure, Fijalkow, Nathanael, Jurdzinski, Marcin, Lazic, Ranko and Parys, Pawel (2019) Universal trees grow inside separating automata : quasi-polynomial lower bounds for parity games. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), California, 6-9 Jan 2019. Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 2333-2349. ISBN 9781611975482. doi:10.1137/1.9781611975482.142

Daviaud, Laure, Jurdzinski, Marcin and Lehtinen, Karolina (2019) Alternating weak automata from universal trees. In: 30th International Conference on Concurrency Theory (CONCUR 2019) , Amsterdam, the Netherlands, 26-31 Aug 2019. Published in: 30th International Conference on Concurrency Theory (CONCUR 2019), 140 pp. 1-14. ISBN 9783959771214 . doi:10.4230/LIPIcs.CONCUR.2019.18

2018

Daviaud, Laure, Jurdzinski, Marcin and Lazic, Ranko (2018) A pseudo-quasi-polynomial algorithm for mean-payoff parity games. In: 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Oxford, 9–12 Jul 2018. Published in: LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science pp. 325-334. ISBN 9781450355834. doi:10.1145/3209108.3209162

Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2018) Distributed methods for computing approximate equilibria. Algorithmica . doi:10.1007/s00453-018-0465-y

Daviaud, Laure, Jurdzinski, Marcin, Lazic, Ranko, Mazowiecki, Filip, Pérez, Guillermo A. and Worell, James (2018) When is containment decidable for probabilistic automata? In: ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9-13 Jul 2018. Published in: Proceedings of 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) pp. 1-15. doi:10.4230/LIPIcs.ICALP.2018.379 (In Press)

2017

Colcombet, Thomas , Jurdzinski, Marcin, Lazic, Ranko and Schmitz, Sylvain (2017) Perfect half space games. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017. Published in: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) ISBN 9781509030187. doi:10.1109/LICS.2017.8005105

Jurdzinski, Marcin and Lazic, Ranko (2017) Succinct progress measures for solving parity games. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017. Published in: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) pp. 1-9. ISBN 9781509030187. doi:10.1109/LICS.2017.8005092

2016

Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2016) Distributed methods for computing approximate equilibria. In: International Conference on Web and Internet Economics, WINE 2016, Montréal, Canada, 11-14 Dec 2016. Published in: Web and Internet Economics. WINE 2016, 10123 pp. 15-28. ISBN 9783662541098. ISSN 0302-9743. doi:10.1007/978-3-662-54110-4_2

2015

Jurdzinski, Marcin, Lazic, Ranko and Schmitz, Sylvain (2015) Fixed-dimensional energy games are in pseudo-polynomial time. In: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, 9135 pp. 260-272. ISBN 9783662476659. ISSN 0302-9743. doi:10.1007/978-3-662-47666-6_21

2014

Czumaj, Artur, Fasoulakis, Michail and Jurdzinski, Marcin (2014) Approximate well-supported Nash equilibria in symmetric bimatrix games. In: Lavi, Ron, (ed.) Algorithmic Game Theory : 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. Lecture Notes in Computer Science, Volume 8768 . Springer Berlin Heidelberg, pp. 244-254. ISBN 9783662448021

2013

Demri, Stéphane P., Jurdzinski, Marcin, Lachish, Oded and Lazic, Ranko (2013) The covering and boundedness problems for branching vector addition systems. Journal of Computer and System Sciences, 79 (1). pp. 23-38. doi:10.1016/j.jcss.2012.04.002

Fearnley, J. and Jurdzinski, Marcin (2013) Reachability in two-clock timed automata is PSPACE-complete. In: Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David, (eds.) Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II. Lecture Notes in Computer Science, Volume 7966 . Berlin ; London: Springer Berlin Heidelberg, pp. 212-223. ISBN 9783642392115

2011

Rutkowski, Michał, Ph.D., Lazić, Ranko and Jurdzinski, Marcin (2011) Average-price-per-reward games on hybrid automata with strong resets. International Journal on Software Tools for Technology Transfer, Vol.13 (No.6). pp. 553-569. doi:10.1007/s10009-010-0180-8

Jurdzinski, Marcin and Lazic, Ranko (2011) Alternating automata on data trees and XPath satisfiability. ACM Transactions on Computational Logic (TOCL), Volume 12 (Number 3). pp. 1-21. doi:10.1145/1929954.1929956

2010

Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2010) Linear complementarity algorithms for infinite games. In: 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, January 23-29, 2010. Published in: Lecture Notes in Computer Science, Vol.5901 pp. 382-393. ISBN 978-3-642-11265-2. ISSN 0302-9743. doi:10.1007/978-3-642-11266-9

2009

Jurdzinski, Marcin (2009) Algorithms for solving infinite games. In: 35th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, January 24-30, 2009. Published in: Lecture Notes in Computer Science, Vol.5404 pp. 46-48. ISBN 978-3-540-95890-1. ISSN 0302-9743. doi:10.1007/978-3-540-95891-8_7

Lazic, Ranko, Jurdzinski, Marcin and Rutkowski, Michał, Ph.D. (2009) Average-price-per-reward games on hybrid automata with strong resets. In: Jones, Neil D. and Müller-Olm, Markus, (eds.) Verification, Model Checking, and Abstract Interpretation. Lecture Notes in Computer Science (5403). London: Springer, pp. 167-181. ISBN 9783540938996

Jurdzinski, Marcin, Kwiatkowska, Marta, Norman, Gethin and Trivedi, Ashutosh (2009) Concavely-priced probabilistic timed automata. In: 30th International Conference on Concurrency Theory, Bologna, Italy, September 01-04, 2009. Published in: Lecture Notes in Computer Science, Vol.5710 pp. 415-430. ISBN 978-3-642-04080-1. ISSN 0302-9743. doi:10.1007/978-3-642-04081-8_28

2008

Bouyer, Patricia, Brihaye, Thomas, Jurdzinski, Marcin, Lazic, Ranko and Rutkowski, Michał, Ph.D. (2008) Average-price and reachability-price games on hybrid automata with strong resets. In: 6th International Conference on Formal Modeling and Analysis of Timed Systems, St Malo, France, 15-17 September, 2008. Published in: Lecture Notes in Computer Science, 5215 pp. 63-77. ISBN 9783540857778. ISSN 0302-9743. doi:10.1007/978-3-540-85778-5_6

Jurdzinski, Marcin and Trivedi, Ashutosh (2008) Average-time games. In: 28th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Bangalore, India, 9-11 Dec 2008. Published in: Leibniz International Proceedings in Informatics, Vol.2 pp. 340-351. ISSN 1868-8969. doi:10.4230/LIPIcs.FSTTCS.2008.1765

Jurdzinski, Marcin and Trivedi, Ashutosh (2008) Concavely-Priced Timed Automata (Extended Abstract). In: 6th International Conference on Formal Modeling and Analysis of Timed Systems, St Malo, France, Sep 15-17, 2008. Published in: Lecture Notes in Computer Science, Vol.5215 pp. 48-62. ISBN 978-3-540-85777-8. ISSN 0302-9743. doi:10.1007/978-3-540-85778-5

Jurdzinski, Marcin, Laroussinie, Francois and Sproston, Jeremy (2008) Model checking probabilistic timed automata with one or two clocks. Logical Methods in Computer Science, Vol.4 (No.3). Article no.12 . doi:10.2168/LMCS-4(3:12)2008

Jurdzinski, Marcin, Paterson, Michael S. and Zwick, Uri (2008) A deterministic subexponential algorithm for solving parity games. SIAM Journal on Computing, Vol.38 (No.4). pp. 1519-1532. doi:10.1137/070686652

Jurdzinski, Marcin and Savani, Rahul (2008) A simple P-matrix linear complementarity problem for discounted games. In: 4th Conference on Computability in Europe (CiE 2008), Athens, Greece, 15-20 Jun 2008. Published in: Logic and Theory of Algorithms, 5028 pp. 283-293. ISBN 9783540694052. ISSN 0302-9743. doi:10.1007/978-3-540-69407-6_32

2007

Jurdzinski, Marcin and Lazic, Ranko (2007) Alternation-free modal mu-calculus for data trees. In: 22nd Annual IEEE Symposium on Logic in Computer Science , Wroclaw, Poland, 10-14 Jul 2007. Published in: 22nd Annual IEEE Symposium on Logic in Computer Science : proceedings : Wroc¿aw, Poland, 10-14 July, 2007 pp. 131-140. ISBN 9780769529080. ISSN 1043-6871.

Jurdzinski, Marcin, Laroussinie, Francois and Sproston, Jeremy (2007) Modd checking probabilistic timed automata with one or two clocks. In: Grumberg, O. and Huth, M., (eds.) Tools and Algorithms for the Construction and Analysis of Systems : 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007 Braga, Portugal, March 24 - April 1, 2007. Proceed. Lecture Notes in Computer Science, Volume 4424 . Springer Verlag, pp. 170-184. ISBN 9783540712084

Jurdzinski, Marcin and Trivedi, Ashutosh (2007) Reachability-time games on timed automata. In: 34th International Colloquium on Automata, Languages and Programming, Wroclaw, Poland, 9-13 Jul 2007. Published in: Automata, Languages and Programming, Proceedings, Volume 4596 pp. 838-849. ISBN 9783540734192. ISSN 0302-9743.

2006

Chatterjee, Krishnendu, Henzinger, Thomas A. and Jurdzinski, Marcin (2006) Games with secure equilibria. In: 3rd International Symposium on Formal Methods for Components and Objects, Leiden, Netherlands, 2-05 Nov 2004. Published in: Theoretical Computer Science, 365 (1-2). pp. 67-82. ISSN 0304-3975. doi:10.1016/j.tcs.2006.07.032

Jurdzinski, Marcin, Peled, Doron and Qu, Hongyang (2006) Calculating probabilities of real-time test cases. In: 5th International Workshop on Formal Approaches to Software Testing (FATES 2005), Edinburgh, 11 Jul 2005. Published in: Formal Approaches to Software Testing, 3997 pp. 134-151. ISBN 3540344543. ISSN 0302-9743.

Jurdzinski, Marcin, Paterson, Michael S. and Zwick, Uri (2006) A deterministic subexponential algorithm for solving parity games. In: 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, Jan 2006. Published in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 117-123. ISBN 978-0-89871-605-4. ISSN 9780898716054.