Skip to main content
What types of page to search?

Popular pages: Undergraduate Postgraduate PhD Accommodation Research International students

Alternatively use our A-Z index.

Dr Rasmus Ibsen-Jensen


Algorithms and Computing Systems
Part of
School of Computer Science and Informatics
Faculty of Science and Engineering

Contact

R.Ibsen-Jensen@liverpool.ac.uk

Research outputs

Selected research outputs

  1. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components (Journal article - 2018)
  2. The Big Match with a Clock and a Bit of Memory (Conference Paper - 2018)
  3. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components (Conference Paper - 2016)
  4. The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games (Conference Paper - 2015)
  5. Computational complexity of ecological and evolutionary spatial dynamics (Journal article - 2015)
What type of research output do you want to show?

2026

The Complexity of Games with Randomised Control

Preprint

2025

2024

2023

Games on Graphs.

Fijalkow, N., Bertrand, N., Bouyer-Decitre, P., Brenguier, R., Carayol, A., Fearnley, J., . . . Skomra, M. (2023). Games on Graphs.. CoRR, abs/2305.10546.

Journal article

2022

Complexity of Spatial Games

Chatterjee, K., Ibsen-Jensen, R., Jecker, I., & Svoboda, J. (2022). Complexity of Spatial Games. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 250. doi:10.4230/LIPIcs.FSTTCS.2022.11

DOI
10.4230/LIPIcs.FSTTCS.2022.11
Conference Paper

2021

2020

One-Clock Priced Timed Games are PSPACE-hard

Fearnley, J., Ibsen-Jensen, R., & Savani, R. (2020). One-Clock Priced Timed Games are PSPACE-hard. LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Retrieved from http://arxiv.org/abs/2001.04458v2

Journal article

All-Pay Bidding Games on Graphs

Avni, G., Ibsen-Jensen, R., & Tkadlec, J. (2020). All-Pay Bidding Games on Graphs. THIRTY-FOURTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THE THIRTY-SECOND INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE AND THE TENTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 34, 1798-1805. Retrieved from https://www.webofscience.com/

Journal article

All-Pay Bidding Games on Graphs.

Avni, G., Ibsen-Jensen, R., & Tkadlec, J. (2020). All-Pay Bidding Games on Graphs.. In AAAI (pp. 1798-1805). AAAI Press. Retrieved from https://ojs.aaai.org/index.php/AAAI/issue/view/249

Conference Paper

One-Clock Priced Timed Games are PSPACE-hard.

Fearnley, J., Ibsen-Jensen, R., & Savani, R. (2020). One-Clock Priced Timed Games are PSPACE-hard.. In H. Hermanns, L. Zhang, N. Kobayashi, & D. Miller (Eds.), LICS (pp. 397-409). ACM. Retrieved from https://doi.org/10.1145/3373718

Conference Paper

Optimal and Perfectly Parallel Algorithms for On-demand Data-Flow Analysis.

Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2020). Optimal and Perfectly Parallel Algorithms for On-demand Data-Flow Analysis.. In P. Müller (Ed.), ESOP Vol. 12075 (pp. 112-140). Springer. Retrieved from https://doi.org/10.1007/978-3-030-44914-8

Conference Paper

2019

2018

Infinite-Duration Poorman-Bidding Games.

Avni, G., Henzinger, T. A., & Ibsen-Jensen, R. (2018). Infinite-Duration Poorman-Bidding Games.. In G. Christodoulou, & T. Harks (Eds.), WINE Vol. 11316 (pp. 21-36). Springer. Retrieved from https://doi.org/10.1007/978-3-030-04612-5

Conference Paper

2017

Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs

DOI
10.48550/arxiv.1706.06931
Preprint

A short proof of correctness of the quasi-polynomial time algorithm for parity games

DOI
10.48550/arxiv.1702.01953
Preprint

2016

Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components

Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2016). Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. In ACM SIGPLAN NOTICES Vol. 51 (pp. 733-747). doi:10.1145/2914770.2837624

DOI
10.1145/2914770.2837624
Conference Paper

Algorithms for algebraic path properties in concurrent systems of constant treewidth components

Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2016). Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (pp. 733-747). ACM. doi:10.1145/2837614.2837624

DOI
10.1145/2837614.2837624
Conference Paper

Robust draws in balanced knockout tournaments

Chatterjee, K., Ibsen-Jensen, R., & Tkadlec, J. (2016). Robust draws in balanced knockout tournaments. In Ijcai International Joint Conference on Artificial Intelligence Vol. 2016-January (pp. 172-179).

Conference Paper

2015

Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components

DOI
10.48550/arxiv.1510.07565
Preprint

Qualitative analysis of concurrent mean-payoff games

Chatterjee, K., & Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean-payoff games. INFORMATION AND COMPUTATION, 242, 2-24. doi:10.1016/j.ic.2015.03.009

DOI
10.1016/j.ic.2015.03.009
Journal article

Strategy Complexity of Concurrent Stochastic Games with Safety and Reachability Objectives

DOI
10.48550/arxiv.1506.02434
Preprint

Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth

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. doi:10.1145/2775051.2676979

DOI
10.1145/2775051.2676979
Journal article

Edit Distance for Pushdown Automata

Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit Distance for Pushdown Automata. In Lecture Notes in Computer Science (pp. 121-133). Springer Berlin Heidelberg. doi:10.1007/978-3-662-47666-6_10

DOI
10.1007/978-3-662-47666-6_10
Chapter

Edit distance for pushdown automata

Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit Distance for Pushdown Automata. Automata, Languages, and Programming, 9135, 121-133. doi:10.1007/978-3-662-47666-6_10

DOI
10.23638/LMCS-13(3:23)2017
Journal article

2014

The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games

DOI
10.48550/arxiv.1409.6690
Preprint

Edit distance for timed automata

Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2014). Edit distance for timed automata. In Proceedings of the 17th international conference on Hybrid systems: computation and control (pp. 303-312). ACM. doi:10.1145/2562059.2562141

DOI
10.1145/2562059.2562141
Conference Paper

Faster Algorithms for Algebraic Path Properties in RSMs with Constant Treewidth.

Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A., & Goyal, P. (2014). Faster Algorithms for Algebraic Path Properties in RSMs with Constant Treewidth.. CoRR, abs/1410.7724.

Journal article

Generalized Risk-Aversion in Stochastic Multi-Armed Bandits.

Zimin, A., Ibsen-Jensen, R., & Chatterjee, K. (2014). Generalized Risk-Aversion in Stochastic Multi-Armed Bandits.. CoRR, abs/1405.0833.

Journal article

The Complexity of Ergodic Mean-payoff Games

Chatterjee, K., & Ibsen-Jensen, R. (2014). The Complexity of Ergodic Mean-payoff Games. In AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT II Vol. 8573 (pp. 122-133). Retrieved from https://www.webofscience.com/

Conference Paper

The Complexity of Ergodic Mean-payoff Games.

Chatterjee, K., & Ibsen-Jensen, R. (2014). The Complexity of Ergodic Mean-payoff Games.. CoRR, abs/1404.5734.

Journal article

The Complexity of Solving Reachability Games Using Value and Strategy Iteration

Hansen, K. A., Ibsen-Jensen, R., & Miltersen, P. B. (2014). The Complexity of Solving Reachability Games Using Value and Strategy Iteration. THEORY OF COMPUTING SYSTEMS, 55(2), 380-403. doi:10.1007/s00224-013-9524-6

DOI
10.1007/s00224-013-9524-6
Journal article

2013

Patience of matrix games

Hansen, K. A., Ibsen-Jensen, R., Podolskii, V. V., & Tsigaridas, E. (2013). Patience of matrix games. Discrete Applied Mathematics, 161(16-17), 2440-2459. doi:10.1016/j.dam.2013.05.008

DOI
10.1016/j.dam.2013.05.008
Journal article

A Faster Algorithm for Solving One-Clock Priced Timed Games

Hansen, T. D., Ibsen-Jensen, R., & Miltersen, P. B. (2013). A Faster Algorithm for Solving One-Clock Priced Timed Games. In Unknown Conference (pp. 531-545). Springer Berlin Heidelberg. doi:10.1007/978-3-642-40184-8_37

DOI
10.1007/978-3-642-40184-8_37
Conference Paper

The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games

Hansen, T. D., & Ibsen-Jensen, R. (2013). The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games. In Unknown Conference (pp. 252-262). Springer Berlin Heidelberg. doi:10.1007/978-3-642-39053-1_29

DOI
10.1007/978-3-642-39053-1_29
Conference Paper

The complexity of interior point methods for solving discounted turn-based stochastic games

DOI
10.48550/arxiv.1304.1888
Preprint

Strategy Complexity of Finite-Horizon Markov Decision Processes and Simple Stochastic Games

Chatterjee, K., & Ibsen-Jensen, R. (2013). Strategy Complexity of Finite-Horizon Markov Decision Processes and Simple Stochastic Games. In Unknown Conference (pp. 106-117). Springer Berlin Heidelberg. doi:10.1007/978-3-642-36046-6_11

DOI
10.1007/978-3-642-36046-6_11
Conference Paper

2012

Solving Simple Stochastic Games with Few Coin Toss Positions

Ibsen-Jensen, R., & Miltersen, P. B. (2012). Solving Simple Stochastic Games with Few Coin Toss Positions. In ALGORITHMS - ESA 2012 Vol. 7501 (pp. 636-647). Retrieved from https://www.webofscience.com/

Conference Paper

Strategy complexity of finite-horizon Markov decision processes and simple stochastic games

DOI
10.48550/arxiv.1209.3617
Preprint

2011

The Complexity of Solving Reachability Games Using Value and Strategy Iteration

Hansen, K. A., Ibsen-Jensen, R., & Miltersen, P. B. (2011). The Complexity of Solving Reachability Games Using Value and Strategy Iteration. In Unknown Conference (pp. 77-90). Springer Berlin Heidelberg. doi:10.1007/978-3-642-20712-9_7

DOI
10.1007/978-3-642-20712-9_7
Conference Paper

2010