Modern Graph Algorithmic Techniques in Formal Verification
Project Period: 2011-09-01 – 2015-08-31
Externally Funded
Principal Investigator
Krishnendu Chatterjee
Department(s)
Chatterjee Group
Grant Number
P 23499-N23
Funding Organisation
FWF
129 Publications
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.
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).
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.
2016 | Conference Paper | IST-REx-ID: 1138 |
Quantitative automata under probabilistic semantics
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings of the 31st Annual ACM/IEEE Symposium, IEEE, 2016, pp. 76–85.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings of the 31st Annual ACM/IEEE Symposium, IEEE, 2016, pp. 76–85.
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).
2016 | Conference Paper | IST-REx-ID: 1324
Indefinite-horizon reachability in Goal-DEC-POMDPs
K. Chatterjee, M. Chmelik, in:, Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, 2016, pp. 88–96.
View
| Download None (ext.)
K. Chatterjee, M. Chmelik, in:, Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, 2016, pp. 88–96.
2016 | Conference Paper | IST-REx-ID: 1327 |
Stochastic shortest path with energy constraints in POMDPs
T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.
View
| Download Preprint (ext.)
T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.
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.
2015 | Journal Article | IST-REx-ID: 1501 |
CEGAR for compositional analysis of qualitative properties in Markov decision processes
K. Chatterjee, M. Chmelik, P. Daca, Formal Methods in System Design 47 (2015) 230–264.
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, M. Chmelik, P. Daca, Formal Methods in System Design 47 (2015) 230–264.
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 | Journal Article | IST-REx-ID: 1624 |
Cellular cooperation with shift updating and repulsion
A. Pavlogiannis, K. Chatterjee, B. Adlam, M. Nowak, Scientific Reports 5 (2015).
View
| Files available
| DOI
A. Pavlogiannis, K. Chatterjee, B. Adlam, M. Nowak, Scientific Reports 5 (2015).
2015 | Journal Article | IST-REx-ID: 1665 |
Mutations driving CLL and their evolution in progression and relapse
Landau D, Tausch E, Taylor Weiner A, Stewart C, Reiter J, Bahlo J, Kluth S, Božić I, Lawrence M, Böttcher S, Carter S, Cibulskis K, Mertens D, Sougnez C, Rosenberg M, Hess J, Edelmann J, Kless S, Kneba M, Ritgen M, Fink A, Fischer K, Gabriel S, Lander E, Nowak M, Döhner H, Hallek M, Neuberg D, Getz G, Stilgenbauer S, Wu C. 2015. Mutations driving CLL and their evolution in progression and relapse. Nature. 526(7574), 525–530.
View
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
Landau D, Tausch E, Taylor Weiner A, Stewart C, Reiter J, Bahlo J, Kluth S, Božić I, Lawrence M, Böttcher S, Carter S, Cibulskis K, Mertens D, Sougnez C, Rosenberg M, Hess J, Edelmann J, Kless S, Kneba M, Ritgen M, Fink A, Fischer K, Gabriel S, Lander E, Nowak M, Döhner H, Hallek M, Neuberg D, Getz G, Stilgenbauer S, Wu C. 2015. Mutations driving CLL and their evolution in progression and relapse. Nature. 526(7574), 525–530.
2015 | Journal Article | IST-REx-ID: 1673 |
Amplifiers of selection
B. Adlam, K. Chatterjee, M. Nowak, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 471 (2015).
View
| Files available
| DOI
B. Adlam, K. Chatterjee, M. Nowak, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 471 (2015).
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 | Conference Paper | IST-REx-ID: 1691
Temporal logic motion planning using POMDPs with parity objectives: Case study paper
M. Svoreňová, M. Chmelik, K. Leahy, H. Eniser, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 233–238.
View
| DOI
M. Svoreňová, M. Chmelik, K. Leahy, H. Eniser, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 233–238.
2015 | Journal Article | IST-REx-ID: 1694
Quantitative temporal simulation and refinement distances for timed systems
K. Chatterjee, V. Prabhu, IEEE Transactions on Automatic Control 60 (2015) 2291–2306.
View
| DOI
K. Chatterjee, V. Prabhu, IEEE Transactions on Automatic Control 60 (2015) 2291–2306.
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.
2015 | Journal Article | IST-REx-ID: 1709 |
Biological auctions with multiple rewards
J. Reiter, A. Kanodia, R. Gupta, M. Nowak, K. Chatterjee, Proceedings of the Royal Society of London Series B Biological Sciences 282 (2015).
View
| Files available
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
J. Reiter, A. Kanodia, R. Gupta, M. Nowak, K. Chatterjee, Proceedings of the Royal Society of London Series B Biological Sciences 282 (2015).
2015 | Conference Paper | IST-REx-ID: 1820 |
Optimal cost almost-sure reachability in POMDPs
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp. 3496–3502.
View
| Files available
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp. 3496–3502.
2015 | Conference Paper | IST-REx-ID: 1838 |
Assume-guarantee synthesis for concurrent reactive programs with partial information
R. Bloem, K. Chatterjee, S. Jacobs, R. Könighofer, in:, Springer, 2015, pp. 517–532.
View
| DOI
| Download Preprint (ext.)
R. Bloem, K. Chatterjee, S. Jacobs, R. Könighofer, in:, Springer, 2015, pp. 517–532.
2015 | Conference Paper | IST-REx-ID: 1839 |
Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, 9035 (2015) 181–187.
View
| DOI
| Download Preprint (ext.)
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, 9035 (2015) 181–187.
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: 2187 |
Synthesizing robust systems
R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, G. Hofferek, B. Jobstmann, B. Könighofer, R. Könighofer, Acta Informatica 51 (2014) 193–220.
View
| Files available
| DOI
R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, G. Hofferek, B. Jobstmann, B. Könighofer, R. Könighofer, Acta Informatica 51 (2014) 193–220.
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.
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 | Conference Paper | IST-REx-ID: 2819 |
Quantitative timed simulation functions and refinement metrics for real-time systems
K. Chatterjee, V. Prabhu, in:, Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, Springer, 2013, pp. 273–282.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, V. Prabhu, in:, Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, Springer, 2013, pp. 273–282.
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.
2012 | Journal Article | IST-REx-ID: 2848 |
Evolutionary game dynamics in populations with different learners
K. Chatterjee, D. Zufferey, M. Nowak, Journal of Theoretical Biology 301 (2012) 161–173.
View
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
K. Chatterjee, D. Zufferey, M. Nowak, Journal of Theoretical Biology 301 (2012) 161–173.
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.
2012 | Conference Paper | IST-REx-ID: 2916 |
Interface Simulation Distances
P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, 2012, pp. 29–42.
View
| Files available
| DOI
| Download Submitted Version (ext.)
| arXiv
P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, 2012, pp. 29–42.
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.
2012 | Conference Paper | IST-REx-ID: 2936 |
Finite automata with time delay blocks
K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Roceedings of the Tenth ACM International Conference on Embedded Software, ACM, 2012, pp. 43–52.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Roceedings of the Tenth ACM International Conference on Embedded Software, ACM, 2012, pp. 43–52.
2012 | Conference Paper | IST-REx-ID: 2947 |
Equivalence of games with probabilistic uncertainty and partial observation games
K. Chatterjee, M. Chmelik, R. Majumdar, in:, Springer, 2012, pp. 385–399.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, M. Chmelik, R. Majumdar, in:, Springer, 2012, pp. 385–399.
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).
2012 | Conference Paper | IST-REx-ID: 3252 |
Synthesizing protocols for digital contract signing
K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 152–168.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 152–168.
2012 | Journal Article | IST-REx-ID: 3254
The complexity of stochastic Müller games
K. Chatterjee, Information and Computation 211 (2012) 29–48.
View
| DOI
| Download None (ext.)
K. Chatterjee, Information and Computation 211 (2012) 29–48.
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.
2012 | Journal Article | IST-REx-ID: 3128 |
A survey of partial-observation stochastic parity games
K. Chatterjee, L. Doyen, T.A. Henzinger, Formal Methods in System Design 43 (2012) 268–284.
View
| Files available
| DOI
K. Chatterjee, L. Doyen, T.A. Henzinger, Formal Methods in System Design 43 (2012) 268–284.
2012 | Journal Article | IST-REx-ID: 3260 |
Evolutionary dynamics of biological auctions
K. Chatterjee, J. Reiter, M. Nowak, Theoretical Population Biology 81 (2012) 69–80.
View
| Files available
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
K. Chatterjee, J. Reiter, M. Nowak, Theoretical Population Biology 81 (2012) 69–80.
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.
2011 | Conference Paper | IST-REx-ID: 3346 |
Two views on multiple mean payoff objectives in Markov Decision Processes
T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, in:, IEEE, 2011.
View
| DOI
| Download Submitted Version (ext.)
T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, in:, IEEE, 2011.
2018 | Conference Paper | IST-REx-ID: 34 |
Sensor synthesis for POMDPs with reachability objectives
K. Chatterjee, M. Chemlík, U. Topcu, in:, AAAI Press, 2018, pp. 47–55.
View
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chemlík, U. Topcu, in:, AAAI Press, 2018, pp. 47–55.
2012 | Journal Article | IST-REx-ID: 2972 |
Energy parity games
K. Chatterjee, L. Doyen, Theoretical Computer Science 458 (2012) 49–60.
View
| Files available
| DOI
| arXiv
K. Chatterjee, L. Doyen, Theoretical Computer Science 458 (2012) 49–60.
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: 419 |
Partners and rivals in direct reciprocity
C. Hilbe, K. Chatterjee, M. Nowak, Nature Human Behaviour 2 (2018) 469–477.
View
| Files available
| DOI
C. Hilbe, K. Chatterjee, M. Nowak, Nature Human Behaviour 2 (2018) 469–477.
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).
2015 | Conference Paper | IST-REx-ID: 1661 |
Improved algorithms for one-pair and k-pair Streett objectives
K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.
View
| Files available
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.
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.
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.
2012 | Conference Paper | IST-REx-ID: 497 |
Faster algorithms for alternating refinement relations
K. Chatterjee, S. Chaubal, P. Kamath, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–182.
View
| Files available
| DOI
K. Chatterjee, S. Chaubal, P. Kamath, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–182.
2012 | Conference Paper | IST-REx-ID: 3165 |
An O(n2) time algorithm for alternating Büchi games
K. Chatterjee, M.H. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.
View
| Files available
| DOI
| Download None (ext.)
| arXiv
K. Chatterjee, M.H. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.
2012 | Conference Paper | IST-REx-ID: 2956
Mean payoff pushdown games
K. Chatterjee, Y. Velner, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.
View
| Files available
| DOI
K. Chatterjee, Y. Velner, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.
2012 | Conference Paper | IST-REx-ID: 2955 |
Partial-observation stochastic games: How to win when belief fails
K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.
2012 | Conference Paper | IST-REx-ID: 3341 |
Robustness of structurally equivalent concurrent parity games
K. Chatterjee, in:, Springer, 2012, pp. 270–285.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, in:, Springer, 2012, pp. 270–285.
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).
2012 | Conference Paper | IST-REx-ID: 2957 |
Decidable problems for probabilistic automata on infinite words
K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.
2013 | Conference Paper | IST-REx-ID: 2000 |
TTP: Tool for tumor progression
J. Reiter, I. Božić, K. Chatterjee, M. Nowak, in:, Proceedings of 25th Int. Conf. on Computer Aided Verification, Springer, 2013, pp. 101–106.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
J. Reiter, I. Božić, K. Chatterjee, M. Nowak, in:, Proceedings of 25th Int. Conf. on Computer Aided Verification, Springer, 2013, pp. 101–106.
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.
2013 | Conference Paper | IST-REx-ID: 1376
Distributed synthesis for LTL fragments
K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25.
2015 | Conference Paper | IST-REx-ID: 1481 |
Automatic generation of alternative starting positions for simple traditional board games
U. Ahmed, K. Chatterjee, S. Gulwani, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 745–752.
View
| Files available
| Download None (ext.)
U. Ahmed, K. Chatterjee, S. Gulwani, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 745–752.
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.
2016 | Journal Article | IST-REx-ID: 1529 |
Optimal cost almost-sure reachability in POMDPs
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Artificial Intelligence 234 (2016) 26–48.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Artificial Intelligence 234 (2016) 26–48.
2017 | Journal Article | IST-REx-ID: 1066
Quantitative fair simulation games
K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Information and Computation 254 (2017) 143–166.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Information and Computation 254 (2017) 143–166.
2017 | Journal Article | IST-REx-ID: 466 |
Unifying two views on multiple mean-payoff objectives in Markov decision processes
K. Chatterjee, Z. Křetínská, J. Kretinsky, Logical Methods in Computer Science 13 (2017).
View
| Files available
| DOI
K. Chatterjee, Z. Křetínská, J. Kretinsky, Logical Methods in Computer Science 13 (2017).
2015 | Conference Paper | IST-REx-ID: 1657
Unifying two views on multiple mean-payoff objectives in Markov decision processes
K. Chatterjee, Z. Komárková, J. Kretinsky, (2015) 244–256.
View
| Files available
| DOI
K. Chatterjee, Z. Komárková, J. Kretinsky, (2015) 244–256.
2015 | Conference Paper | IST-REx-ID: 1656
Nested weighted automata
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.
View
| Files available
| DOI
| arXiv
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.
2017 | Journal Article | IST-REx-ID: 467 |
Nested weighted automata
K. Chatterjee, T.A. Henzinger, J. Otop, ACM Transactions on Computational Logic (TOCL) 18 (2017).
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, T.A. Henzinger, J. Otop, ACM Transactions on Computational Logic (TOCL) 18 (2017).
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.
2016 | Conference Paper | IST-REx-ID: 1166
A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps
K. Chatterjee, M. Chmelik, J. Davies, in:, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, 2016, pp. 3225–3232.
View
| Files available
K. Chatterjee, M. Chmelik, J. Davies, in:, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, 2016, pp. 3225–3232.
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 | Journal Article | IST-REx-ID: 10416 |
Optimal Dyck reachability for data-dependence and Alias analysis
K. Chatterjee, B. Choudhary, A. Pavlogiannis, Proceedings of the ACM on Programming Languages 2 (2017).
View
| Files available
| DOI
| arXiv
K. Chatterjee, B. Choudhary, A. Pavlogiannis, Proceedings of the ACM on Programming Languages 2 (2017).
2017 | Journal Article | IST-REx-ID: 10417 |
Data-centric dynamic partial order reduction
M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Proceedings of the ACM on Programming Languages 2 (2017).
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Proceedings of the ACM on Programming Languages 2 (2017).
2015 | Conference Paper | IST-REx-ID: 1603 |
Counterexample explanation by learning small strategies in Markov decision processes
T. Brázdil, K. Chatterjee, M. Chmelik, A. Fellner, J. Kretinsky, in:, Springer, 2015, pp. 158–177.
View
| Files available
| DOI
| Download Preprint (ext.)
T. Brázdil, K. Chatterjee, M. Chmelik, A. Fellner, J. Kretinsky, in:, Springer, 2015, pp. 158–177.
2016 | Conference Paper | IST-REx-ID: 1438 |
Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, in:, ACM, 2016, pp. 327–342.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, in:, ACM, 2016, pp. 327–342.