Efficient Algorithms for Computer Aided Verification

Project Period: 2016-03-15 – 2020-03-14
Externally Funded
Principal Investigator
Krishnendu Chatterjee
Department(s)
Chatterjee Group
Grant Number
ICT15-003
Funding Organisation
WWTF

34 Publications

2018 | Conference Paper | IST-REx-ID: 143   OA
Efficient algorithms for asymptotic bounds on termination time in VASS
T. Brázdil, K. Chatterjee, A. Kučera, P. Novotny, D. Velan, F. Zuleger, in:, IEEE, 2018, pp. 185–194.
View | DOI | Download (ext.)
 
2018 | Conference Paper | IST-REx-ID: 66   OA
Ergodic mean-payoff games for the analysis of attacks in crypto-currencies.
K. Chatterjee, A. Goharshady, R. Ibsen-Jensen, Y. Velner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 11.
View | Files available | DOI | Download (ext.) | arXiv
 
2016 | Conference Paper | IST-REx-ID: 1182   OA
Robust draws in balanced knockout tournaments
K. Chatterjee, R. Ibsen-Jensen, J. Tkadlec, in:, AAAI Press, 2016, pp. 172–179.
View | Files available | Download (ext.)
 
2018 | Conference Paper | IST-REx-ID: 25
Goal-HSVI: Heuristic search value iteration for goal-POMDPs
K. Horák, B. Bošanský, K. Chatterjee, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4764–4770.
View | DOI
 
2018 | Conference Paper | IST-REx-ID: 311   OA
Quantitative analysis of smart contracts
K. Chatterjee, A. Goharshady, Y. Velner, in:, Springer, 2018, pp. 739–767.
View | Files available | DOI
 
2017 | Conference Paper | IST-REx-ID: 645   OA
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 (ext.)
 
2019 | Conference Paper | IST-REx-ID: 6175   OA
Cost analysis of nondeterministic probabilistic programs
P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019), Association for Computing Machinery, 2019, pp. 204–220.
View | Files available | DOI | arXiv
 
2016 | Conference Paper | IST-REx-ID: 1090   OA
Nested weighted limit-average automata of bounded width
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
View | Files available | DOI
 
2017 | Journal Article | IST-REx-ID: 464   OA
Improved algorithms for parity and Streett objectives
K. Chatterjee, M. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).
View | Files available | DOI
 
2018 | Conference Paper | IST-REx-ID: 5679   OA
New approaches for almost-sure termination of probabilistic programs
M. Huang, H. Fu, K. Chatterjee, in:, S. Ryu (Ed.), Springer, 2018, pp. 181–201.
View | DOI | Download (ext.) | arXiv
 
2018 | Preprint | IST-REx-ID: 5977   OA
Computational Approaches for Stochastic Shortest Path on Succinct MDPs
K. Chatterjee, H. Fu, A. Goharshady, N. Okati, ArXiv (n.d.).
View | Download (ext.) | arXiv
 
2017 | Conference Paper | IST-REx-ID: 628   OA
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 (ext.)
 
2017 | Conference Paper | IST-REx-ID: 6519   OA
Improved set-based symbolic algorithms for parity games
K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017, p. 18.
View | Files available | DOI
 
2017 | Conference Paper | IST-REx-ID: 1009   OA
Optimizing expectation with guarantees in POMDPs
K. Chatterjee, P. Novotny, 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 (ext.)
 
2016 | Conference Paper | IST-REx-ID: 1340   OA
The big match in small space
K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 64–76.
View | DOI | Download (ext.)
 
2018 | Conference Paper | IST-REx-ID: 24   OA
Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives
K. Chatterjee, A. Elgyütt, P. Novotny, O. Rouillé, in:, IJCAI, 2018, pp. 4692–4699.
View | DOI | Download (ext.) | arXiv
 
2018 | Conference Paper | IST-REx-ID: 310   OA
Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety and diameter
K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, ACM, 2018, pp. 2341–2356.
View | DOI | Download (ext.) | arXiv
 
2014 | Journal Article | IST-REx-ID: 2141 View | Files available | DOI | Download (ext.)
 
2016 | Conference Paper | IST-REx-ID: 480   OA
Perfect-information stochastic games with generalized mean-payoff objectives
K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256.
View | DOI | Download (ext.)
 
2019 | Conference Paper | IST-REx-ID: 5948
Termination of nondeterministic probabilistic programs
H. Fu, K. Chatterjee, 11388 (2019) 468–490.
View | DOI
 
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 | DOI
 
2018 | Conference Paper | IST-REx-ID: 6340   OA
Secure Credit Reporting on the Blockchain
A.K. Goharshady, A. Behrouz, K. Chatterjee, in:, Proceedings of the IEEE International Conference on Blockchain, IEEE, 2018, pp. 1343–1348.
View | Files available | arXiv
 
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 | DOI
 
2016 | Conference Paper | IST-REx-ID: 1068   OA
Conditionally optimal algorithms for generalized Büchi Games
K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
View | Files available | DOI
 
2016 | Conference Paper | IST-REx-ID: 1070   OA
Computation tree logic for synchronization properties
K. Chatterjee, L. Doyen, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.
View | Files available | DOI
 
2016 | Conference Paper | IST-REx-ID: 1138   OA
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 (ext.)
 
2016 | Conference Paper | IST-REx-ID: 1140   OA
Model and objective separation with conditional lower bounds disjunction is harder than conjunction
K. Chatterjee, W. Dvoák, M. Henzinger, V. Loitzenbauer, in:, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206.
View | DOI | Download (ext.)
 
2016 | Conference Paper | IST-REx-ID: 1335   OA
Quantitative monitor automata
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 23–38.
View | DOI | Download (ext.)
 
2018 | Conference Paper | IST-REx-ID: 141   OA
Symbolic algorithms for graphs and Markov decision processes with fairness objectives
K. Chatterjee, M. Henzinger, V. Loitzenbauer, S. Oraee, V. Toman, in:, Springer, 2018, pp. 178–197.
View | Files available | DOI
 
2018 | Conference Paper | IST-REx-ID: 297   OA
Strategy representation by decision trees in reactive synthesis
T. Brázdil, K. Chatterjee, J. Kretinsky, V. Toman, in:, Springer, 2018, pp. 385–407.
View | Files available | DOI
 
2014 | Conference Paper | IST-REx-ID: 475   OA
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
 
2019 | Journal Article | IST-REx-ID: 6380   OA
Efficient parameterized algorithms for data packing
K. Chatterjee, A.K. Goharshady, N. Okati, A. Pavlogiannis, Proceedings of the ACM on Programming Languages 3 (2019) 53.
View | Files available | DOI
 
2019 | Conference Paper | IST-REx-ID: 6378   OA
Hybrid Mining: Exploiting blockchain’s computational power for distributed problem solving
K. Chatterjee, A.K. Goharshady, A. Pourdamghani, in:, Proceedings of the 34th ACM Symposium on Applied Computing, ACM, n.d., pp. 374–381.
View | Files available | DOI
 
2019 | Conference Paper | IST-REx-ID: 6056   OA
Probabilistic smart contracts: Secure randomness on the blockchain
K. Chatterjee, A.K. Goharshady, A. Pourdamghani, in:, IEEE International Conference on Blockchain and Cryptocurrency, IEEE, 2019, p. 8751326.
View | DOI | Download (ext.) | arXiv