publications

My publications by categories and in reversed chronological order. See also my DBLP page for a current list of my outputs.

2025

  1. Resolving Nondeterminism by Chance
    Soumyajit Paul, David Purser, Sven Schewe, Qiyi Tang, Patrick Totzke, and Di-De Yen
    Apr 2025
  2. HyperLTL Satisfiability Is Highly Undecidable, HyperCTL^* is Even Harder
    Logical Methods in Computer Science , Jan 2025

2024

  1. Temporal Explorability Games
    Dec 2024
  2. Optimally Controlling a Random Population
    Hugo Gimbert, Corto Mascle, and Patrick Totzke
    Dec 2024
  3. Strategy Complexity of Büchi Objectives in Concurrent Stochastic Games
    Dec 2024
  4. History-deterministic Timed Automata
    Logical Methods in Computer Science , Oct 2024
  5. Strategy Complexity of Reachability in Countable Stochastic 2-Player Games
    Dynamic Games and Applications, Sep 2024
  6. The Power of Counting Steps in Quantitative Games
    Sougata Bose, Rasmus Ibsen-Jensen, David Purser, Patrick Totzke, and Pierre Vandenhove
    In International Conference on Concurrency Theory (CONCUR), Aug 2024
  7. Bounded-Memory Strategies in Partial-Information Games
    Sougata Bose, Rasmus Ibsen-Jensen, and Patrick Totzke
    In ACM/IEEE Symposium on Logic in Computer Science (LICS), Jul 2024
  8. Memoryless Strategies in Stochastic Reachability Games
    Mar 2024
  9. Parity Games on Temporal Graphs
    Pete Austin, Sougata Bose, and Patrick Totzke
    In International Conference on Foundations of Software Science and Computational Structures (FoSSaCS), Apr 2024

2023

  1. History-Deterministic Vector Addition Systems
    Sougata Bose, David Purser, and Patrick Totzke
    In International Conference on Concurrency Theory (CONCUR), Apr 2023
  2. Handling of Past and Future with Phenesthe+
    Manolis Pitsikalis, Alexei Lisitsa, Patrick Totzke, and Simon Lee
    In International Symposium on Games, Automata, Logics, and Formal Verification (GandALF), Apr 2023

2022

  1. History-deterministic Timed Automata are Not Determinizable
    In International Workshop on Reachability Problems (RP), Apr 2022
  2. History-deterministic Timed Automata
    In International Conference on Concurrency Theory (CONCUR), Apr 2022
  3. Making Sense of Heterogeneous Maritime Data
    Manolis Pitsikalis, Alexei Lisitsa, Patrick Totzke, and Simon Lee
    In International Conference on Mobile Data Management (MDM), Apr 2022

2021

  1. The Reachability Problem for Two-Dimensional Vector Addition Systems with States
    Journal of the ACM, Aug 2021
  2. Transience in Countable MDPs
    In International Conference on Concurrency Theory (CONCUR), Aug 2021
  3. HyperLTL Satisfiability is \(\Sigma_1^1\)-complete, HyperCTL* Satisfiability is \(\Sigma_1^2\)-complete
    In International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2021
  4. Simple Stochastic Games with Almost Sure Energy-Parity Objectives
    Richard Mayr, Sven Schewe, Patrick Totzke, and Dominik Wojtczak
    In International Conference on Foundations of Software Science and Computational Structures (FoSSaCS), Aug 2021

2020

  1. Optimally Resilient Strategies in Pushdown Safety Games
    Daniel Neider, Patrick Totzke, and Martin Zimmermann
    In International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2020
  2. How to Play in Infinite MDPs (Invited)
    In International Colloquium on Automata, Languages and Programming (ICALP), Aug 2020
  3. Strategy Complexity of Parity Objectives in Countable MDPs
    In International Conference on Concurrency Theory (CONCUR), Aug 2020
  4. Parametrized Universality Problems for One-Counter Nets
    Shaull Almagor, Udi Boker, Piotr Hofman, and Patrick Totzke
    In International Conference on Concurrency Theory (CONCUR), Aug 2020

2019

  1. Controlling a Random Population is EXPTIME-hard
    Corto Mascle, Mahsa Shirmohammadi, and Patrick Totzke
    Aug 2019
  2. Timed Basic Parallel Processes
    Lorenzo Clemente, Piotr Hofman, and Patrick Totzke
    In International Conference on Concurrency Theory (CONCUR), Aug 2019
  3. Büchi Objectives in Countable MDPs
    In International Colloquium on Automata, Languages and Programming (ICALP), Aug 2019

2018

  1. Universal Safety for Timed Petri Nets is PSPACE-complete
    Parosh Aziz Abdulla, Mohamed Faouzi Atig, Radu Ciobanu, Richard Mayr, and Patrick Totzke
    In International Conference on Concurrency Theory (CONCUR), Aug 2018

2017

  1. What Makes Petri Nets Harder to Verify: Stack or Data?
    Ranko Lazić and Patrick Totzke
    Aug 2017
  2. Trace inclusion for one-counter nets revisited
    Piotr Hofman and Patrick Totzke
    Theoretical Computer Science, Aug 2017
  3. MDPs with Energy-Parity Objectives
    Richard Mayr, Sven Schewe, Patrick Totzke, and Dominik Wojtczak
    In ACM/IEEE Symposium on Logic in Computer Science (LICS), Aug 2017
  4. Linear Combinations of Unordered Data Vectors
    Piotr Hofman, Jérôme Leroux, and Patrick Totzke
    In ACM/IEEE Symposium on Logic in Computer Science (LICS), Aug 2017

2016

  1. Branching-Time Model Checking Gap-Order Constraint Systems
    Richard Mayr and Patrick Totzke
    Fundamenta Informaticae, Aug 2016
  2. Simulation Problems Over One-Counter Nets
    Piotr Hofman, Slawomir Lasota, Richard Mayr, and Patrick Totzke
    Logical Methods in Computer Science , Aug 2016
  3. Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
    Matthias Englert, Ranko Lazić, and Patrick Totzke
    In ACM/IEEE Symposium on Logic in Computer Science (LICS), Aug 2016
  4. Coverability Trees for Petri Nets with Unordered Data
    In International Conference on Foundations of Software Science and Computational Structures (FoSSaCS), Aug 2016
  5. A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One
    In International Colloquium on Automata, Languages and Programming (ICALP), Aug 2016

2015

  1. On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
    Jérôme Leroux, Grégoire Sutre, and Patrick Totzke
    In International Colloquium on Automata, Languages and Programming (ICALP), Aug 2015
  2. On Boundedness Problems for Pushdown Vector Addition Systems
    Jérôme Leroux, Grégoire Sutre, and Patrick Totzke
    In International Workshop on Reachability Problems (RP), Aug 2015

2014

  1. Trace Inclusion for One-Counter Nets Revisited
    Piotr Hofman and Patrick Totzke
    In International Workshop on Reachability Problems (RP), Aug 2014
  2. Infinite-State Energy Games
    Parosh Aziz Abdulla, Mohamed Faouzi Atig, Piotr Hofman, Richard Mayr, K. Narayan Kumar, and Patrick Totzke
    In ACM/IEEE Symposium on Logic in Computer Science (LICS), Aug 2014
  3. Inclusion Problems for One-Counter Systems
    Patrick Totzke
    University of Edinburgh, Apr 2014

2013

  1. Simulation Over One-Counter Nets is PSPACE-Complete
    Piotr Hofman, Sławomir Lasota, Richard Mayr, and Patrick Totzke
    In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2013
  2. Branching-Time Model Checking Gap-Order Constraint Systems
    Richard Mayr and Patrick Totzke
    In International Workshop on Reachability Problems (RP), Nov 2013
  3. Decidability of Weak Simulation on One-Counter Nets
    Piotr Hofman, Richard Mayr, and Patrick Totzke
    In ACM/IEEE Symposium on Logic in Computer Science (LICS), Feb 2013

2012

  1. Approximating Weak Bisimilarity of Basic Parallel Processes
    Piotr Hofman and Patrick Totzke
    In International Workshop on Expressiveness in Concurrency (EXPRESS), Sep 2012

2009

  1. Properties of Multiset Language Classes Defined by Multiset Pushdown Automata
    Manfred Kudlek, Patrick Totzke, and Georg Zetzsche
    Fundamenta Informaticae, Sep 2009
  2. Multiset Pushdown Automata
    Manfred Kudlek, Patrick Totzke, and Georg Zetzsche
    Fundamenta Informaticae, Sep 2009
  3. Multiset Rewriting – A Formal Language Theoretic Perspective on Concurrent Systems
    Patrick Totzke
    Universität Hamburg, Oct 2009


Software

All my software tools are accessible through my Github profile. See here for a recent attempt at solving Energy Games. I am the main developer and maintainer of alot, a terminal MUA for the notmuch mail indexer. I also wrote LaTeX beamer themes designed after the websites of the Universities of Edinburgh and Warwick, which I used for some of my talks.