Game Theory
Project Period: 2015-03-01 – 2019-08-31
Externally Funded
Acronym
SHINE
Principal Investigator
Krishnendu Chatterjee
Department(s)
Chatterjee Group
Grant Number
S11407
Funding Organisation
FWF
97 Publications
2021 | Conference Paper | IST-REx-ID: 10002 |

Symbolic time and space tradeoffs for probabilistic verification
K. Chatterjee, W. Dvorak, M.H. Henzinger, A. Svozil, in:, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Institute of Electrical and Electronics Engineers, 2021, pp. 1–13.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, W. Dvorak, M.H. Henzinger, A. Svozil, in:, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Institute of Electrical and Electronics Engineers, 2021, pp. 1–13.
2017 | Conference Paper | IST-REx-ID: 1009 |

Optimizing expectation with guarantees in POMDPs
K. Chatterjee, P. Novotný, G. Pérez, J. Raskin, D. Zikelic, in:, Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI Press, 2017, pp. 3725–3732.
View
| Download Submitted Version (ext.)
K. Chatterjee, P. Novotný, G. Pérez, J. Raskin, D. Zikelic, in:, Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI Press, 2017, pp. 3725–3732.
2017 | Conference Paper | IST-REx-ID: 1011 |

Faster algorithms for weighted recursive state machines
K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.), Springer, 2017, pp. 287–313.
View
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.), Springer, 2017, pp. 287–313.
2019 | Conference Paper | IST-REx-ID: 10190 |

Value-centric dynamic partial order reduction
K. Chatterjee, A. Pavlogiannis, V. Toman, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM, 2019.
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
K. Chatterjee, A. Pavlogiannis, V. Toman, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM, 2019.
2017 | Journal Article | IST-REx-ID: 1065 |

Pushdown reachability with constant treewidth
K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
View
| Files available
| DOI
K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
2015 | Conference Paper | IST-REx-ID: 10796
The value 1 problem under finite-memory strategies for concurrent mean-payoff games
K. Chatterjee, R. Ibsen-Jensen, in:, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2015, pp. 1018–1029.
View
| DOI
| arXiv
K. Chatterjee, R. Ibsen-Jensen, in:, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2015, pp. 1018–1029.
2017 | Journal Article | IST-REx-ID: 1080 |

Reconstructing metastatic seeding patterns of human cancers
J. Reiter, A. Makohon Moore, J. Gerold, I. Božić, K. Chatterjee, C. Iacobuzio Donahue, B. Vogelstein, M. Nowak, Nature Communications 8 (2017).
View
| Files available
| DOI
J. Reiter, A. Makohon Moore, J. Gerold, I. Božić, K. Chatterjee, C. Iacobuzio Donahue, B. Vogelstein, M. Nowak, Nature Communications 8 (2017).
2018 | Conference Paper | IST-REx-ID: 10883 |

Quasipolynomial set-based symbolic algorithms for parity games
K. Chatterjee, W. Dvořák, M.H. Henzinger, A. Svozil, in:, 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, EasyChair, 2018, pp. 233–253.
View
| Files available
| DOI
| arXiv
K. Chatterjee, W. Dvořák, M.H. Henzinger, A. Svozil, in:, 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, EasyChair, 2018, pp. 233–253.
2014 | Conference Paper | IST-REx-ID: 10884 |

Parameterized model checking of token-passing systems
B. Aminof, S. Jacobs, A. Khalimov, S. Rubin, in:, Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 262–281.
View
| DOI
| Download Preprint (ext.)
| arXiv
B. Aminof, S. Jacobs, A. Khalimov, S. Rubin, in:, Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 262–281.
2013 | Conference Paper | IST-REx-ID: 10902
How to travel between languages
K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg, 2013, pp. 214–225.
View
| DOI
K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg, 2013, pp. 214–225.
2022 | Journal Article | IST-REx-ID: 12257 |

Social balance on networks: Local minima and best-edge dynamics
K. Chatterjee, J. Svoboda, D. Zikelic, A. Pavlogiannis, J. Tkadlec, Physical Review E 106 (2022).
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, J. Svoboda, D. Zikelic, A. Pavlogiannis, J. Tkadlec, Physical Review E 106 (2022).
2013 | Conference Paper | IST-REx-ID: 1374 |

Infinite-state games with finitary conditions
K. Chatterjee, N. Fijalkow, in:, 22nd EACSL Annual Conference on Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–196.
View
| Files available
| DOI
K. Chatterjee, N. Fijalkow, in:, 22nd EACSL Annual Conference on Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–196.
2014 | Journal Article | IST-REx-ID: 1375 |

Approximating the minimum cycle mean
K. Chatterjee, M.H. Henzinger, S. Krinninger, V. Loitzenbauer, M. Raskin, Theoretical Computer Science 547 (2014) 104–116.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M.H. Henzinger, S. Krinninger, V. Loitzenbauer, M. Raskin, Theoretical Computer Science 547 (2014) 104–116.
2018 | Journal Article | IST-REx-ID: 157 |

Evolution of cooperation in stochastic games
C. Hilbe, Š. Šimsa, K. Chatterjee, M. Nowak, Nature 559 (2018) 246–249.
View
| Files available
| DOI
C. Hilbe, Š. Šimsa, K. Chatterjee, M. Nowak, Nature 559 (2018) 246–249.
2015 | Conference Paper | IST-REx-ID: 1609 |

The complexity of synthesis from probabilistic components
K. Chatterjee, L. Doyen, M. Vardi, in:, 42nd International Colloquium, Springer Nature, 2015, pp. 108–120.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, L. Doyen, M. Vardi, in:, 42nd International Colloquium, Springer Nature, 2015, pp. 108–120.
2015 | Conference Paper | IST-REx-ID: 1689 |

Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 259–268.
View
| Files available
| DOI
| Download Preprint (ext.)
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 259–268.
2017 | Journal Article | IST-REx-ID: 1407 |

Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.
2015 | Journal Article | IST-REx-ID: 1698 |

The complexity of multi-mean-payoff and multi-energy games
Y. Velner, K. Chatterjee, L. Doyen, T.A. Henzinger, A. Rabinovich, J. Raskin, Information and Computation 241 (2015) 177–196.
View
| DOI
| Download Preprint (ext.)
Y. Velner, K. Chatterjee, L. Doyen, T.A. Henzinger, A. Rabinovich, J. Raskin, Information and Computation 241 (2015) 177–196.
2014 | Conference Paper | IST-REx-ID: 1869
Suraq - a controller synthesis tool using uninterpreted functions
G. Hofferek, A. Gupta, in:, E. Yahav (Ed.), HVC 2014, Springer, 2014, pp. 68–74.
View
| DOI
G. Hofferek, A. Gupta, in:, E. Yahav (Ed.), HVC 2014, Springer, 2014, pp. 68–74.
2014 | Conference Paper | IST-REx-ID: 2027 |

Verification of markov decision processes using learning algorithms
T. Brázdil, K. Chatterjee, M. Chmelik, V. Forejt, J. Kretinsky, M. Kwiatkowska, D. Parker, M. Ujma, in:, F. Cassez, J.-F. Raskin (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Society of Industrial and Applied Mathematics, 2014, pp. 98–114.
View
| DOI
| Download Submitted Version (ext.)
T. Brázdil, K. Chatterjee, M. Chmelik, V. Forejt, J. Kretinsky, M. Kwiatkowska, D. Parker, M. Ujma, in:, F. Cassez, J.-F. Raskin (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Society of Industrial and Applied Mathematics, 2014, pp. 98–114.
2015 | Journal Article | IST-REx-ID: 2034 |

Probabilistic opacity for Markov decision processes
B. Bérard, K. Chatterjee, N. Sznajder, Information Processing Letters 115 (2015) 52–59.
View
| DOI
| Download Preprint (ext.)
B. Bérard, K. Chatterjee, N. Sznajder, Information Processing Letters 115 (2015) 52–59.
2014 | Journal Article | IST-REx-ID: 2234 |

Markov decision processes with multiple long-run average objectives
T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, Logical Methods in Computer Science 10 (2014).
View
| Files available
| DOI
| Download Published Version (ext.)
T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, Logical Methods in Computer Science 10 (2014).
2013 | Conference Paper | IST-REx-ID: 2305 |

Trading performance for stability in Markov decision processes
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, in:, 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–340.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, in:, 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–340.
2017 | Journal Article | IST-REx-ID: 1294 |

Trading performance for stability in Markov decision processes
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, Journal of Computer and System Sciences 84 (2017) 144–170.
View
| Files available
| DOI
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, Journal of Computer and System Sciences 84 (2017) 144–170.
2013 | Conference Paper | IST-REx-ID: 2446 |

Automata with generalized Rabin pairs for probabilistic model checking and LTL synthesis
K. Chatterjee, A. Gaiser, J. Kretinsky, 8044 (2013) 559–575.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, A. Gaiser, J. Kretinsky, 8044 (2013) 559–575.
2013 | Conference Paper | IST-REx-ID: 2444 |

Faster algorithms for Markov decision processes with low treewidth
K. Chatterjee, J. Ła̧Cki, 8044 (2013) 543–558.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, J. Ła̧Cki, 8044 (2013) 543–558.
2012 | Conference Paper | IST-REx-ID: 2715 |

Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–473.
View
| Files available
| DOI
K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–473.
2015 | Journal Article | IST-REx-ID: 1598 |

Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
K. Chatterjee, M. Joglekar, N. Shah, Theoretical Computer Science 573 (2015) 71–89.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Joglekar, N. Shah, Theoretical Computer Science 573 (2015) 71–89.
2012 | Conference Paper | IST-REx-ID: 10904
Strategy synthesis for multi-dimensional quantitative objectives
K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.), CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.
View
| Files available
| DOI
| arXiv
K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.), CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.
2014 | Journal Article | IST-REx-ID: 2716 |

Strategy synthesis for multi-dimensional quantitative objectives
K. Chatterjee, M. Randour, J. Raskin, Acta Informatica 51 (2014) 129–163.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Randour, J. Raskin, Acta Informatica 51 (2014) 129–163.
2013 | Journal Article | IST-REx-ID: 2814 |

The complexity of coverage
K. Chatterjee, L. Alfaro, R. Majumdar, International Journal of Foundations of Computer Science 24 (2013) 165–185.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, L. Alfaro, R. Majumdar, International Journal of Foundations of Computer Science 24 (2013) 165–185.
2013 | Journal Article | IST-REx-ID: 2817 |

Density games
S. Novak, K. Chatterjee, M. Nowak, Journal of Theoretical Biology 334 (2013) 26–34.
View
| Files available
| DOI
S. Novak, K. Chatterjee, M. Nowak, Journal of Theoretical Biology 334 (2013) 26–34.
2013 | Journal Article | IST-REx-ID: 2824
Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems
K. Chatterjee, V. Prabhu, Information and Computation 228–229 (2013) 83–119.
View
| DOI
K. Chatterjee, V. Prabhu, Information and Computation 228–229 (2013) 83–119.
2013 | Journal Article | IST-REx-ID: 2836 |

Assume-guarantee synthesis for digital contract signing
K. Chatterjee, V. Raman, Formal Aspects of Computing 26 (2013) 825–859.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, V. Raman, Formal Aspects of Computing 26 (2013) 825–859.
2013 | Journal Article | IST-REx-ID: 2854 |

Strategy improvement for concurrent reachability and turn based stochastic safety games
K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System Sciences 79 (2013) 640–657.
View
| Files available
| DOI
K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System Sciences 79 (2013) 640–657.
2013 | Journal Article | IST-REx-ID: 2858 |

The effect of one additional driver mutation on tumor progression
J. Reiter, I. Božić, B. Allen, K. Chatterjee, M. Nowak, Evolutionary Applications 6 (2013) 34–45.
View
| Files available
| DOI
J. Reiter, I. Božić, B. Allen, K. Chatterjee, M. Nowak, Evolutionary Applications 6 (2013) 34–45.
2013 | Conference Paper | IST-REx-ID: 2886 |

Controllable-choice message sequence graphs
M. Chmelik, V. Řehák, 7721 (2013) 118–130.
View
| DOI
| Download Submitted Version (ext.)
M. Chmelik, V. Řehák, 7721 (2013) 118–130.
2014 | Journal Article | IST-REx-ID: 1733 |

Interface simulation distances
P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 560 (2014) 348–363.
View
| Files available
| DOI
| Download Submitted Version (ext.)
P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 560 (2014) 348–363.
2014 | Journal Article | IST-REx-ID: 2141 |

Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
K. Chatterjee, M.H. Henzinger, Journal of the ACM 61 (2014).
View
| Files available
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, M.H. Henzinger, Journal of the ACM 61 (2014).
2014 | Conference Paper | IST-REx-ID: 2054
Qualitative concurrent parity games: Bounded rationality
K. Chatterjee, in:, P. Baldan, D. Gorla (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 544–559.
View
| Files available
| DOI
K. Chatterjee, in:, P. Baldan, D. Gorla (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 544–559.
2015 | Journal Article | IST-REx-ID: 1731 |

Randomness for free
K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, Information and Computation 245 (2015) 3–16.
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, Information and Computation 245 (2015) 3–16.
2013 | Journal Article | IST-REx-ID: 2831 |

Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives
K. Chatterjee, M.H. Henzinger, M. Joglekar, N. Shah, Formal Methods in System Design 42 (2013) 301–327.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M.H. Henzinger, M. Joglekar, N. Shah, Formal Methods in System Design 42 (2013) 301–327.
2015 | Journal Article | IST-REx-ID: 1856 |

Measuring and synthesizing systems in probabilistic environments
K. Chatterjee, T.A. Henzinger, B. Jobstmann, R. Singh, Journal of the ACM 62 (2015).
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, T.A. Henzinger, B. Jobstmann, R. Singh, Journal of the ACM 62 (2015).
2018 | Journal Article | IST-REx-ID: 454 |

Crosstalk in concurrent repeated games impedes direct reciprocity and requires stronger levels of forgiveness
J. Reiter, C. Hilbe, D. Rand, K. Chatterjee, M. Nowak, Nature Communications 9 (2018).
View
| Files available
| DOI
J. Reiter, C. Hilbe, D. Rand, K. Chatterjee, M. Nowak, Nature Communications 9 (2018).
2017 | Journal Article | IST-REx-ID: 464 |

Improved algorithms for parity and Streett objectives
K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).
View
| Files available
| DOI
| arXiv
K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).
2014 | Conference Paper | IST-REx-ID: 475 |

First cycle games
B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.
View
| Files available
| DOI
B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.
2015 | Journal Article | IST-REx-ID: 523 |

Looking at mean-payoff and total-payoff through windows
K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.
2012 | Conference Paper | IST-REx-ID: 10905 |

Polynomial-time algorithms for energy games with special weight structures
K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, Algorithms – ESA 2012, Springer, 2012, pp. 301–312.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, Algorithms – ESA 2012, Springer, 2012, pp. 301–312.
2014 | Journal Article | IST-REx-ID: 535 |

Polynomial-time algorithms for energy games with special weight structures
K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica 70 (2014) 457–492.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica 70 (2014) 457–492.
2014 | Conference Paper | IST-REx-ID: 1903
Partial-observation stochastic reachability and parity games
K. Chatterjee, in:, Springer, 2014, pp. 1–4.
View
| Files available
| DOI
K. Chatterjee, in:, Springer, 2014, pp. 1–4.
2014 | Journal Article | IST-REx-ID: 2038 |

Temporal specifications with accumulative values
U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 15 (2014).
View
| Files available
| DOI
U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 15 (2014).
2013 | Conference Paper | IST-REx-ID: 2295 |

What is decidable about partially observable Markov decision processes with omega-regular objectives
K. Chatterjee, M. Chmelik, M. Tracol, 23 (2013) 165–180.
View
| Files available
| DOI
K. Chatterjee, M. Chmelik, M. Tracol, 23 (2013) 165–180.
2014 | Conference Paper | IST-REx-ID: 2162 |

The complexity of ergodic mean payoff games
K. Chatterjee, R. Ibsen-Jensen, in:, Springer, 2014, pp. 122–133.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, R. Ibsen-Jensen, in:, Springer, 2014, pp. 122–133.
2016 | Journal Article | IST-REx-ID: 1477 |

What is decidable about partially observable Markov decision processes with ω-regular objectives
K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.
2014 | Conference Paper | IST-REx-ID: 2213 |

The complexity of partial-observation stochastic parity games with finite-memory strategies
K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257.
2014 | Conference Paper | IST-REx-ID: 2212
Perfect-information stochastic mean-payoff parity games
K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, in:, Springer, 2014, pp. 210–225.
View
| Files available
| DOI
K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, in:, Springer, 2014, pp. 210–225.
2014 | Conference Paper | IST-REx-ID: 2063
CEGAR for qualitative analysis of probabilistic systems
K. Chatterjee, M. Chmelik, P. Daca, in:, Springer, 2014, pp. 473–490.
View
| Files available
| DOI
K. Chatterjee, M. Chmelik, P. Daca, in:, Springer, 2014, pp. 473–490.
2014 | Conference Paper | IST-REx-ID: 2163 |

Games with a weak adversary
K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121.
2015 | Conference Paper | IST-REx-ID: 1732 |

Qualitative analysis of POMDPs with temporal logic specifications for robotics applications
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, IEEE, 2015, pp. 325–330.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, IEEE, 2015, pp. 325–330.
2017 | Journal Article | IST-REx-ID: 465 |

Edit distance for pushdown automata
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Logical Methods in Computer Science 13 (2017).
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Logical Methods in Computer Science 13 (2017).
2015 | Conference Paper | IST-REx-ID: 1610 |

Edit distance for pushdown automata
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International Colloquium, Springer Nature, 2015, pp. 121–133.
View
| Files available
| DOI
| Download None (ext.)
| arXiv
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International Colloquium, Springer Nature, 2015, pp. 121–133.
2017 | Journal Article | IST-REx-ID: 512 |

Amplification on undirected population structures: Comets beat stars
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Scientific Reports 7 (2017).
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Scientific Reports 7 (2017).
2017 | Conference Paper | IST-REx-ID: 552 |

Faster algorithms for mean-payoff parity games
K. Chatterjee, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
View
| Files available
| DOI
K. Chatterjee, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
2017 | Book Chapter | IST-REx-ID: 625 |

The cost of exactness in quantitative reachability
K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017, pp. 367–381.
View
| Files available
| DOI
K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017, pp. 367–381.
2017 | Conference Paper | IST-REx-ID: 628 |

Automated recurrence analysis for almost linear expected runtime bounds
K. Chatterjee, H. Fu, A. Murhekar, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 118–139.
View
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, H. Fu, A. Murhekar, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 118–139.
2017 | Conference Paper | IST-REx-ID: 645 |

Value iteration for long run average reward in markov decision processes
P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, T. Meggendorfer, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 201–221.
View
| DOI
| Download Submitted Version (ext.)
P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, T. Meggendorfer, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 201–221.
2017 | Journal Article | IST-REx-ID: 653 |

Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer
A. Makohon Moore, M. Zhang, J. Reiter, I. Božić, B. Allen, D. Kundu, K. Chatterjee, F. Wong, Y. Jiao, Z. Kohutek, J. Hong, M. Attiyeh, B. Javier, L. Wood, R. Hruban, M. Nowak, N. Papadopoulos, K. Kinzler, B. Vogelstein, C. Iacobuzio Donahue, Nature Genetics 49 (2017) 358–366.
View
| Files available
| DOI
| PubMed | Europe PMC
A. Makohon Moore, M. Zhang, J. Reiter, I. Božić, B. Allen, D. Kundu, K. Chatterjee, F. Wong, Y. Jiao, Z. Kohutek, J. Hong, M. Attiyeh, B. Javier, L. Wood, R. Hruban, M. Nowak, N. Papadopoulos, K. Kinzler, B. Vogelstein, C. Iacobuzio Donahue, Nature Genetics 49 (2017) 358–366.
2017 | Journal Article | IST-REx-ID: 671 |

Memory-n strategies of direct reciprocity
C. Hilbe, V. Martinez, K. Chatterjee, M. Nowak, PNAS 114 (2017) 4715–4720.
View
| DOI
| Download Published Version (ext.)
| PubMed | Europe PMC
C. Hilbe, V. Martinez, K. Chatterjee, M. Nowak, PNAS 114 (2017) 4715–4720.
2014 | Conference Paper | IST-REx-ID: 10885
Doomsday equilibria for omega-regular games
K. Chatterjee, L. Doyen, E. Filiot, J.-F. Raskin, in:, VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 78–97.
View
| Files available
| DOI
| arXiv
K. Chatterjee, L. Doyen, E. Filiot, J.-F. Raskin, in:, VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 78–97.
2017 | Journal Article | IST-REx-ID: 681 |

Doomsday equilibria for omega-regular games
K. Chatterjee, L. Doyen, E. Filiot, J. Raskin, Information and Computation 254 (2017) 296–315.
View
| Files available
| DOI
| Download Submitted Version (ext.)
| arXiv
K. Chatterjee, L. Doyen, E. Filiot, J. Raskin, Information and Computation 254 (2017) 296–315.
2019 | Conference Paper | IST-REx-ID: 6887 |

Near-linear time algorithms for Streett objectives in graphs and MDPs
K. Chatterjee, W. Dvorák, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
View
| Files available
| DOI
K. Chatterjee, W. Dvorák, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
2019 | Conference Paper | IST-REx-ID: 6885 |

Long-run average behavior of vector addition systems with states
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
2019 | Conference Paper | IST-REx-ID: 6889 |

Combinations of Qualitative Winning for Stochastic Parity Games
K. Chatterjee, N. Piterman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
View
| Files available
| DOI
K. Chatterjee, N. Piterman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
2019 | Conference Paper | IST-REx-ID: 6942 |

Strategy representation by decision trees with linear classifiers
P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, V. Toman, in:, 16th International Conference on Quantitative Evaluation of Systems, Springer Nature, 2019, pp. 109–128.
View
| DOI
| Download Preprint (ext.)
| arXiv
P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, V. Toman, in:, 16th International Conference on Quantitative Evaluation of Systems, Springer Nature, 2019, pp. 109–128.
2017 | Journal Article | IST-REx-ID: 716 |

The complexity of mean-payoff pushdown games
K. Chatterjee, Y. Velner, Journal of the ACM 64 (2017) 34.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, Y. Velner, Journal of the ACM 64 (2017) 34.
2013 | Conference Paper | IST-REx-ID: 2329 |

Hyperplane separation technique for multidimensional mean-payoff games
K. Chatterjee, Y. Velner, 8052 (2013) 500–515.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, Y. Velner, 8052 (2013) 500–515.
2017 | Journal Article | IST-REx-ID: 717 |

Hyperplane separation technique for multidimensional mean-payoff games
K. Chatterjee, Y. Velner, Journal of Computer and System Sciences 88 (2017) 236–259.
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, Y. Velner, Journal of Computer and System Sciences 88 (2017) 236–259.
2020 | Journal Article | IST-REx-ID: 7212 |

Limits on amplifiers of natural selection under death-Birth updating
J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational Biology 16 (2020).
View
| Files available
| DOI
| arXiv
J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational Biology 16 (2020).
2019 | Conference Paper | IST-REx-ID: 7231 |

Piecewise robust barrier tubes for nonlinear hybrid systems with uncertainty
H. Kong, E. Bartocci, Y. Jiang, T.A. Henzinger, in:, 17th International Conference on Formal Modeling and Analysis of Timed Systems, Springer Nature, 2019, pp. 123–141.
View
| DOI
| Download Preprint (ext.)
| arXiv
H. Kong, E. Bartocci, Y. Jiang, T.A. Henzinger, in:, 17th International Conference on Formal Modeling and Analysis of Timed Systems, Springer Nature, 2019, pp. 123–141.
2018 | Journal Article | IST-REx-ID: 738 |

Automated competitive analysis of real time scheduling with graph games
K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, Real-Time Systems 54 (2018) 166–207.
View
| Files available
| DOI
K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, Real-Time Systems 54 (2018) 166–207.
2013 | Conference Paper | IST-REx-ID: 2820
Automated analysis of real-time scheduling using graph games
K. Chatterjee, A. Kößler, U. Schmid, in:, Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, ACM, 2013, pp. 163–172.
View
| Files available
| DOI
K. Chatterjee, A. Kößler, U. Schmid, in:, Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, ACM, 2013, pp. 163–172.
2022 | Journal Article | IST-REx-ID: 11402 |

Graph planning with expected finite horizon
K. Chatterjee, L. Doyen, Journal of Computer and System Sciences 129 (2022) 1–21.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, L. Doyen, Journal of Computer and System Sciences 129 (2022) 1–21.
2019 | Conference Paper | IST-REx-ID: 8324 |

Proving expected sensitivity of probabilistic programs with randomized variable-dependent termination time
P. Wang, H. Fu, K. Chatterjee, Y. Deng, M. Xu, in:, Proceedings of the ACM on Programming Languages, ACM, 2019.
View
| Files available
| DOI
| arXiv
P. Wang, H. Fu, K. Chatterjee, Y. Deng, M. Xu, in:, Proceedings of the ACM on Programming Languages, ACM, 2019.
2020 | Conference Paper | IST-REx-ID: 8193
Multiple-environment Markov decision processes: Efficient analysis and applications
K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, A. Royer, in:, Proceedings of the 30th International Conference on Automated Planning and Scheduling, Association for the Advancement of Artificial Intelligence, 2020, pp. 48–56.
View
| Files available
K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, A. Royer, in:, Proceedings of the 30th International Conference on Automated Planning and Scheduling, Association for the Advancement of Artificial Intelligence, 2020, pp. 48–56.
2018 | Book Chapter | IST-REx-ID: 86 |

Computing average response time
K. Chatterjee, T.A. Henzinger, J. Otop, in:, M. Lohstroh, P. Derler, M. Sirjani (Eds.), Principles of Modeling, Springer, 2018, pp. 143–161.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, in:, M. Lohstroh, P. Derler, M. Sirjani (Eds.), Principles of Modeling, Springer, 2018, pp. 143–161.
2021 | Journal Article | IST-REx-ID: 8793 |

Optimal strategies for selecting coordinators
M. Zeiner, U. Schmid, K. Chatterjee, Discrete Applied Mathematics 289 (2021) 392–415.
View
| Files available
| DOI
M. Zeiner, U. Schmid, K. Chatterjee, Discrete Applied Mathematics 289 (2021) 392–415.
2020 | Journal Article | IST-REx-ID: 8788
Precedence-aware automated competitive analysis of real-time scheduling
A. Pavlogiannis, N. Schaumberger, U. Schmid, K. Chatterjee, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 3981–3992.
View
| DOI
A. Pavlogiannis, N. Schaumberger, U. Schmid, K. Chatterjee, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 3981–3992.
2022 | Journal Article | IST-REx-ID: 11938 |

On compatible matchings
O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240.
View
| Files available
| DOI
| arXiv
O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240.
2021 | Conference Paper | IST-REx-ID: 9296 |

On compatible matchings
O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.
2022 | Journal Article | IST-REx-ID: 9311 |

Finite-memory strategies in POMDPs with long-run average objectives
K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations Research 47 (2022) 100–119.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations Research 47 (2022) 100–119.
2014 | Journal Article | IST-REx-ID: 2039 |

The time scale of evolutionary innovation
K. Chatterjee, A. Pavlogiannis, B. Adlam, M. Nowak, PLoS Computational Biology 10 (2014).
View
| Files available
| DOI
K. Chatterjee, A. Pavlogiannis, B. Adlam, M. Nowak, PLoS Computational Biology 10 (2014).
2020 | Journal Article | IST-REx-ID: 7426 |

Abstraction based verification of stability of polyhedral switched systems
M. Garcia Soto, P. Prabhakar, Nonlinear Analysis: Hybrid Systems 36 (2020).
View
| Files available
| DOI
M. Garcia Soto, P. Prabhakar, Nonlinear Analysis: Hybrid Systems 36 (2020).
2019 | Conference Paper | IST-REx-ID: 6780 |

Modular verification for almost-sure termination of probabilistic programs
M. Huang, H. Fu, K. Chatterjee, A.K. Goharshady, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications , ACM, 2019.
View
| Files available
| DOI
| arXiv
M. Huang, H. Fu, K. Chatterjee, A.K. Goharshady, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications , ACM, 2019.
2019 | Conference Paper | IST-REx-ID: 6175 |

Cost analysis of nondeterministic probabilistic programs
P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2019, pp. 204–220.
View
| Files available
| DOI
| arXiv
P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2019, pp. 204–220.
2017 | Conference Paper | IST-REx-ID: 639 |

Non-polynomial worst case analysis of recursive programs
K. Chatterjee, H. Fu, A.K. Goharshady, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 41–63.
View
| Files available
| DOI
| Download Submitted Version (ext.)
| arXiv
K. Chatterjee, H. Fu, A.K. Goharshady, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 41–63.
2019 | Journal Article | IST-REx-ID: 7158 |

Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth
K. Chatterjee, A.K. Goharshady, P. Goyal, R. Ibsen-Jensen, A. Pavlogiannis, ACM Transactions on Programming Languages and Systems 41 (2019).
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, P. Goyal, R. Ibsen-Jensen, A. Pavlogiannis, ACM Transactions on Programming Languages and Systems 41 (2019).
2017 | Conference Paper | IST-REx-ID: 949 |

JTDec: A tool for tree decompositions in soot
K. Chatterjee, A.K. Goharshady, A. Pavlogiannis, in:, D. D’Souza (Ed.), Springer, 2017, pp. 59–66.
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, A. Pavlogiannis, in:, D. D’Souza (Ed.), Springer, 2017, pp. 59–66.