Rasmus Ibsen-Jensen
Chatterjee Group
38 Publications
2020 | Conference Paper | IST-REx-ID: 8533 |

Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2020. Simplified game of life: Algorithms and complexity. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 22:1-22:13.
View
| Files available
| DOI
| arXiv
2020 | Conference Paper | IST-REx-ID: 7810 |

Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2020. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. European Symposium on Programming. ESOP: Programming Languages and Systems, LNCS, vol. 12075, 112–140.
View
| Files available
| DOI
2019 | Conference Paper | IST-REx-ID: 6822 |

Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. 2019. Bidding games on Markov decision processes. Proceedings of the 13th International Conference of Reachability Problems. RP: Reachability Problems, LNCS, vol. 11674, 1–12.
View
| Files available
| DOI
2019 | Journal Article | IST-REx-ID: 7158 |

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

Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. 2018. Language acquisition with communication between learners. Journal of the Royal Society Interface. 15(140), 20180073.
View
| Files available
| DOI
2018 | Conference Paper | IST-REx-ID: 5788 |

Avni G, Henzinger TA, Ibsen-Jensen R. 2018. Infinite-duration poorman-bidding games. 14th International Conference on Web and Internet Economics, WINE, LNCS, vol. 11316, 21–36.
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 5967 |

Hansen KA, Ibsen-Jensen R, Neyman A. 2018. The Big Match with a clock and a bit of memory. Proceedings of the 2018 ACM Conference on Economics and Computation - EC ’18. EC: Conference on Economics and Computation, 149–150.
View
| Files available
| DOI
2018 | Journal Article | IST-REx-ID: 6009 |

Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2018. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. ACM Transactions on Programming Languages and Systems. 40(3), 9.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 66 |

Chatterjee K, Goharshady AK, Ibsen-Jensen R, Velner Y. 2018. Ergodic mean-payoff games for the analysis of attacks in crypto-currencies. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 118, 11.
View
| Files available
| DOI
| arXiv
2017 | Journal Article | IST-REx-ID: 465 |

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

Chatterjee K, Ibsen-Jensen R, Nowak M. 2017. Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 61.
View
| Files available
| DOI
2017 | Conference Paper | IST-REx-ID: 553 |

Chatterjee K, Hansen K, Ibsen-Jensen R. 2017. Strategy complexity of concurrent safety games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 55.
View
| Files available
| DOI
| Download Published Version (ext.)
2016 | Conference Paper | IST-REx-ID: 1182 |

Chatterjee K, Ibsen-Jensen R, Tkadlec J. 2016. Robust draws in balanced knockout tournaments. IJCAI: International Joint Conference on Artificial Intelligence vol. 2016–January, 172–179.
View
| Files available
| Download Preprint (ext.)
2016 | Conference Paper | IST-REx-ID: 1340 |

Hansen K, Ibsen-Jensen R, Koucký M. 2016. The big match in small space. SAGT: Symposium on Algorithmic Game Theory, LNCS, vol. 9928, 64–76.
View
| DOI
| Download Preprint (ext.)
2016 | Conference Paper | IST-REx-ID: 478 |

Chatterjee K, Ibsen-Jensen R. 2016. The complexity of deciding legality of a single step of magic: The gathering. ECAI: European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, vol. 285, 1432–1439.
View
| Files available
| DOI
2016 | Conference Paper | IST-REx-ID: 1071 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2016. Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs. ESA: European Symposium on Algorithms, LIPIcs, vol. 57, 28.
View
| Files available
| DOI
2016 | Conference Paper | IST-REx-ID: 1437 |

Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2016. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. POPL: Principles of Programming Languages, POPL, vol. 20–22, 733–747.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Journal Article | IST-REx-ID: 1559 |

Ibsen-Jensen R, Chatterjee K, Nowak M. 2015. Computational complexity of ecological and evolutionary spatial dynamics. PNAS. 112(51), 15636–15641.
View
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
2015 | Journal Article | IST-REx-ID: 524 |

Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Technical Report | IST-REx-ID: 5431 |

Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.
View
| Files available
| DOI
2015 | Conference Paper | IST-REx-ID: 1610
Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata. 9135(Part II), 121–133.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5430 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5437 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5438 |

Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5432 |

Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5440 |

Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5441 |

Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 24p.
View
| Files available
| DOI
2015 | Journal Article | IST-REx-ID: 1602 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A, Goyal P. 2015. Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices. 50(1), 97–109.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Conference Paper | IST-REx-ID: 1607 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs. CAV: Computer Aided Verification, LNCS, vol. 9206, 140–157.
View
| Files available
| DOI
| Download Preprint (ext.)
2014 | Conference Paper | IST-REx-ID: 2162 |

Chatterjee K, Ibsen-Jensen R. 2014. The complexity of ergodic mean payoff games. ICST: International Conference on Software Testing, Verification and Validation, LNCS, vol. 8573, 122–133.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Conference Paper | IST-REx-ID: 2216 |

Chatterjee K, Ibsen-Jensen R, Majumdar R. 2014. Edit distance for timed automata. HSCC: Hybrid Systems - Computation and Control, 303–312.
View
| Files available
| DOI
| Download Submitted Version (ext.)
2014 | Technical Report | IST-REx-ID: 5419 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.
View
| Files available
| DOI
2014 | Technical Report | IST-REx-ID: 5420 |

Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.
View
| Files available
| DOI
2014 | Technical Report | IST-REx-ID: 5427 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition balancing and reachability on low treewidth graphs, IST Austria, 24p.
View
| Files available
| DOI
2014 | Technical Report | IST-REx-ID: 5421 |

Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.
View
| Files available
| DOI
2013 | Technical Report | IST-REx-ID: 5403 |

Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff games, IST Austria, 33p.
View
| Files available
| DOI
2013 | Technical Report | IST-REx-ID: 5404 |

Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p.
View
| Files available
| DOI
2013 | Technical Report | IST-REx-ID: 5409 |

Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata, IST Austria, 12p.
View
| Files available
| DOI
38 Publications
2020 | Conference Paper | IST-REx-ID: 8533 |

Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2020. Simplified game of life: Algorithms and complexity. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 22:1-22:13.
View
| Files available
| DOI
| arXiv
2020 | Conference Paper | IST-REx-ID: 7810 |

Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2020. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. European Symposium on Programming. ESOP: Programming Languages and Systems, LNCS, vol. 12075, 112–140.
View
| Files available
| DOI
2019 | Conference Paper | IST-REx-ID: 6822 |

Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. 2019. Bidding games on Markov decision processes. Proceedings of the 13th International Conference of Reachability Problems. RP: Reachability Problems, LNCS, vol. 11674, 1–12.
View
| Files available
| DOI
2019 | Journal Article | IST-REx-ID: 7158 |

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

Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. 2018. Language acquisition with communication between learners. Journal of the Royal Society Interface. 15(140), 20180073.
View
| Files available
| DOI
2018 | Conference Paper | IST-REx-ID: 5788 |

Avni G, Henzinger TA, Ibsen-Jensen R. 2018. Infinite-duration poorman-bidding games. 14th International Conference on Web and Internet Economics, WINE, LNCS, vol. 11316, 21–36.
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 5967 |

Hansen KA, Ibsen-Jensen R, Neyman A. 2018. The Big Match with a clock and a bit of memory. Proceedings of the 2018 ACM Conference on Economics and Computation - EC ’18. EC: Conference on Economics and Computation, 149–150.
View
| Files available
| DOI
2018 | Journal Article | IST-REx-ID: 6009 |

Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2018. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. ACM Transactions on Programming Languages and Systems. 40(3), 9.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Conference Paper | IST-REx-ID: 66 |

Chatterjee K, Goharshady AK, Ibsen-Jensen R, Velner Y. 2018. Ergodic mean-payoff games for the analysis of attacks in crypto-currencies. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 118, 11.
View
| Files available
| DOI
| arXiv
2017 | Journal Article | IST-REx-ID: 465 |

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

Chatterjee K, Ibsen-Jensen R, Nowak M. 2017. Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 61.
View
| Files available
| DOI
2017 | Conference Paper | IST-REx-ID: 553 |

Chatterjee K, Hansen K, Ibsen-Jensen R. 2017. Strategy complexity of concurrent safety games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 55.
View
| Files available
| DOI
| Download Published Version (ext.)
2016 | Conference Paper | IST-REx-ID: 1182 |

Chatterjee K, Ibsen-Jensen R, Tkadlec J. 2016. Robust draws in balanced knockout tournaments. IJCAI: International Joint Conference on Artificial Intelligence vol. 2016–January, 172–179.
View
| Files available
| Download Preprint (ext.)
2016 | Conference Paper | IST-REx-ID: 1340 |

Hansen K, Ibsen-Jensen R, Koucký M. 2016. The big match in small space. SAGT: Symposium on Algorithmic Game Theory, LNCS, vol. 9928, 64–76.
View
| DOI
| Download Preprint (ext.)
2016 | Conference Paper | IST-REx-ID: 478 |

Chatterjee K, Ibsen-Jensen R. 2016. The complexity of deciding legality of a single step of magic: The gathering. ECAI: European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, vol. 285, 1432–1439.
View
| Files available
| DOI
2016 | Conference Paper | IST-REx-ID: 1071 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2016. Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs. ESA: European Symposium on Algorithms, LIPIcs, vol. 57, 28.
View
| Files available
| DOI
2016 | Conference Paper | IST-REx-ID: 1437 |

Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2016. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. POPL: Principles of Programming Languages, POPL, vol. 20–22, 733–747.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Journal Article | IST-REx-ID: 1559 |

Ibsen-Jensen R, Chatterjee K, Nowak M. 2015. Computational complexity of ecological and evolutionary spatial dynamics. PNAS. 112(51), 15636–15641.
View
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
2015 | Journal Article | IST-REx-ID: 524 |

Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Technical Report | IST-REx-ID: 5431 |

Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.
View
| Files available
| DOI
2015 | Conference Paper | IST-REx-ID: 1610
Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata. 9135(Part II), 121–133.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5430 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5437 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5438 |

Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5432 |

Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5440 |

Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p.
View
| Files available
| DOI
2015 | Technical Report | IST-REx-ID: 5441 |

Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 24p.
View
| Files available
| DOI
2015 | Journal Article | IST-REx-ID: 1602 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A, Goyal P. 2015. Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices. 50(1), 97–109.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Conference Paper | IST-REx-ID: 1607 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs. CAV: Computer Aided Verification, LNCS, vol. 9206, 140–157.
View
| Files available
| DOI
| Download Preprint (ext.)
2014 | Conference Paper | IST-REx-ID: 2162 |

Chatterjee K, Ibsen-Jensen R. 2014. The complexity of ergodic mean payoff games. ICST: International Conference on Software Testing, Verification and Validation, LNCS, vol. 8573, 122–133.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Conference Paper | IST-REx-ID: 2216 |

Chatterjee K, Ibsen-Jensen R, Majumdar R. 2014. Edit distance for timed automata. HSCC: Hybrid Systems - Computation and Control, 303–312.
View
| Files available
| DOI
| Download Submitted Version (ext.)
2014 | Technical Report | IST-REx-ID: 5419 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.
View
| Files available
| DOI
2014 | Technical Report | IST-REx-ID: 5420 |

Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.
View
| Files available
| DOI
2014 | Technical Report | IST-REx-ID: 5427 |

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition balancing and reachability on low treewidth graphs, IST Austria, 24p.
View
| Files available
| DOI
2014 | Technical Report | IST-REx-ID: 5421 |

Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.
View
| Files available
| DOI
2013 | Technical Report | IST-REx-ID: 5403 |

Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff games, IST Austria, 33p.
View
| Files available
| DOI
2013 | Technical Report | IST-REx-ID: 5404 |

Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p.
View
| Files available
| DOI
2013 | Technical Report | IST-REx-ID: 5409 |

Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata, IST Austria, 12p.
View
| Files available
| DOI