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
Funder
FWF

129 Publications

2022 |Published| Journal Article | IST-REx-ID: 11938 | OA
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.
[Published Version] View | Files available | DOI | arXiv
 
2022 |Published| Journal Article | IST-REx-ID: 12257 | OA
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).
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
2021 |Published| Conference Paper | IST-REx-ID: 9296 | OA
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.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2021 |Published| Journal Article | IST-REx-ID: 9640 | OA
Fast and strong amplifiers of natural selection
J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Nature Communications 12 (2021).
[Published Version] View | Files available | DOI | WoS | PubMed | Europe PMC
 
2021 |Published| Journal Article | IST-REx-ID: 9393 | OA
Faster algorithms for quantitative verification in bounded treewidth graphs
K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Formal Methods in System Design 57 (2021) 401–428.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
2021 |Published| Thesis | IST-REx-ID: 10293 | OA
Evolution of cooperation via (in)direct reciprocity under imperfect information
L. Schmid, Evolution of Cooperation via (in)Direct Reciprocity under Imperfect Information, Institute of Science and Technology Austria, 2021.
[Published Version] View | Files available | DOI
 
2020 |Published| Journal Article | IST-REx-ID: 7212 | OA
Limits on amplifiers of natural selection under death-Birth updating
J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational Biology 16 (2020).
[Published Version] View | Files available | DOI | WoS | arXiv
 
2019 |Published| Journal Article | IST-REx-ID: 7210 | OA
Population structure determines the tradeoff between fixation probability and fixation time
J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Communications Biology 2 (2019).
[Published Version] View | Files available | DOI | WoS | PubMed | Europe PMC
 
2019 |Published| Journal Article | IST-REx-ID: 7158 | OA
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).
[Submitted Version] View | Files available | DOI | WoS
 
2018 |Published| Journal Article | IST-REx-ID: 454 | OA
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).
[Published Version] View | Files available | DOI | WoS
 
2018 |Published| Journal Article | IST-REx-ID: 157 | OA
Evolution of cooperation in stochastic games
C. Hilbe, Š. Šimsa, K. Chatterjee, M. Nowak, Nature 559 (2018) 246–249.
[Submitted Version] View | Files available | DOI | WoS
 
2018 |Published| Journal Article | IST-REx-ID: 419 | OA
Partners and rivals in direct reciprocity
C. Hilbe, K. Chatterjee, M. Nowak, Nature Human Behaviour 2 (2018) 469–477.
[Submitted Version] View | Files available | DOI | WoS
 
2018 |Published| Journal Article | IST-REx-ID: 5993 | OA
Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, ACM Transactions on Programming Languages and Systems 40 (2018).
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.) | WoS | arXiv
 
2018 |Published| Conference Paper | IST-REx-ID: 34 | OA
Sensor synthesis for POMDPs with reachability objectives
K. Chatterjee, M. Chemlík, U. Topcu, in:, AAAI Press, 2018, pp. 47–55.
[Preprint] View | Download Preprint (ext.) | WoS | arXiv
 
2018 |Published| Journal Article | IST-REx-ID: 738 | OA
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.
[Published Version] View | Files available | DOI | WoS
 
2018 |Published| Journal Article | IST-REx-ID: 198 | OA
Language acquisition with communication between learners
R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, Journal of the Royal Society Interface 15 (2018).
[Submitted Version] View | Files available | DOI | WoS | PubMed | Europe PMC
 
2018 |Published| Journal Article | IST-REx-ID: 5751 | OA
Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M.A. Nowak, Communications Biology 1 (2018).
[Published Version] View | Files available | DOI | WoS
 
2018 |Published| Journal Article | IST-REx-ID: 2 | OA
Indirect reciprocity with private, noisy, and incomplete information
C. Hilbe, L. Schmid, J. Tkadlec, K. Chatterjee, M. Nowak, PNAS 115 (2018) 12241–12246.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.) | WoS | PubMed | Europe PMC
 
2018 |Published| Journal Article | IST-REx-ID: 6009 | OA
Algorithms for algebraic path properties in concurrent systems of constant treewidth components
K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, ACM Transactions on Programming Languages and Systems 40 (2018).
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
2017 |Published| Journal Article | IST-REx-ID: 464 | OA
Improved algorithms for parity and Streett objectives
K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).
[Published Version] View | Files available | DOI | arXiv
 

Search

Filter Publications

    • Display / Sort

    Export / Embed