Dr Patrick Totzke

Computer Science

+44 (0)151 795 4256
Work email totzke@liverpool.ac.uk
Personal Websitehttps://cgi.csc.liv.ac.uk/~patrick/

Publications

Selected Publications

Büchi Objectives in Countable MDPs (Conference Paper - 2019)
Linear combinations of unordered data vectors (Conference Paper - 2017)
MDPs with energy-parity objectives (Conference Paper - 2017)
Simulation Problems Over One-Counter Nets (Journal article - 2016)

Filter the publication list

Filter list by type

Show all
Journal article
Conference paper
Chapter
Other

2024

Memoryless Strategies in Stochastic Reachability Games (Preprint)

Memoryless Strategies in Stochastic Reachability Games (Chapter)

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2024). Memoryless Strategies in Stochastic Reachability Games. In Taming the Infinities of Concurrency (pp. 225-242). Springer Nature Switzerland. doi:10.1007/978-3-031-56222-8_13

DOI: 10.1007/978-3-031-56222-8_13

Parity Games on Temporal Graphs (Chapter)

Austin, P., Bose, S., & Totzke, P. (2024). Parity Games on Temporal Graphs. In Lecture Notes in Computer Science (pp. 79-98). Springer Nature Switzerland. doi:10.1007/978-3-031-57228-9_5

DOI: 10.1007/978-3-031-57228-9_5

2023

Preface (Journal article)

Bell, P. C., Potapov, I., Schmitz, S., & Totzke, P. (2023). Preface. Fundamenta Informaticae, 189(3-4), i-iii. doi:10.3233/fi-222158

DOI: 10.3233/fi-222158

Parity Games on Temporal Graphs (Preprint)

Handling of Past and Future with Phenesthe+ (Preprint)

Handling of Past and Future with Phenesthe+ (Conference Paper)

Pitsikalis, M., Lisitsa, A., & Totzke, P. (n.d.). Handling of Past and Future with Phenesthe+. In Electronic Proceedings in Theoretical Computer Science Vol. 390 (pp. 33-49). Open Publishing Association. doi:10.4204/eptcs.390.3

DOI: 10.4204/eptcs.390.3

History-Deterministic Vector Addition Systems (Conference Paper)

Bose, S., Purser, D., & Totzke, P. (2023). History-Deterministic Vector Addition Systems. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 279. doi:10.4230/LIPIcs.CONCUR.2023.18

DOI: 10.4230/LIPIcs.CONCUR.2023.18

History-deterministic Vector Addition Systems (Preprint)

History-deterministic Timed Automata (Preprint)

HyperLTL Satisfiability Is Highly Undecidable, HyperCTL* is Even Harder (Preprint)

2022

History-Deterministic Timed Automata Are Not Determinizable (Conference Paper)

Bose, S., Henzinger, T. A., Lehtinen, K., Schewe, S., & Totzke, P. (2022). History-Deterministic Timed Automata Are Not Determinizable. In Unknown Conference (pp. 67-76). Springer International Publishing. doi:10.1007/978-3-031-19135-0_5

DOI: 10.1007/978-3-031-19135-0_5

History-Deterministic Timed Automata (Conference Paper)

Henzinger, T. A., Lehtinen, K., & Totzke, P. (2022). History-Deterministic Timed Automata. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 243. doi:10.4230/LIPIcs.CONCUR.2022.14

DOI: 10.4230/LIPIcs.CONCUR.2022.14

Making Sense of Heterogeneous Maritime Data (Conference Paper)

Pitsikalis, M., Lisitsa, A., Totzke, P., & Lee, S. (2022). Making Sense of Heterogeneous Maritime Data. In 2022 23RD IEEE INTERNATIONAL CONFERENCE ON MOBILE DATA MANAGEMENT (MDM 2022) (pp. 401-406). doi:10.1109/MDM55031.2022.00089

DOI: 10.1109/MDM55031.2022.00089

Strategy Complexity of Reachability in Countable Stochastic 2-Player Games (Preprint)

Preface. (Journal article)

Bell, P. C., Potapov, I., Schmitz, S., & Totzke, P. (2022). Preface.. Fundam. Informaticae, 189.

2021

The Reachability Problem for Two-Dimensional Vector Addition Systems with States (Journal article)

Blondin, M., Englert, M., Finkel, A., Goeller, S., Haase, C., Lazic, R., . . . Totzke, P. (2021). The Reachability Problem for Two-Dimensional Vector Addition Systems with States. JOURNAL OF THE ACM, 68(5). doi:10.1145/3464794

DOI: 10.1145/3464794

Transience in Countable MDPs (Conference Paper)

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2021). Transience in Countable MDPs. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 203. doi:10.4230/LIPIcs.CONCUR.2021.11

DOI: 10.4230/LIPIcs.CONCUR.2021.11

HyperLTL Satisfiability is $\Sigma_1^1$-complete, HyperCTL* Satisfiability is $\Sigma_1^2$-complete (Preprint)

DOI: 10.48550/arxiv.2105.04176

HyperLTL Satisfiability is $Σ_1^1$-complete, HyperCTL* Satisfiability is $Σ_1^2$-complete (Journal article)

Fortin, M., Kuijer, L. B., Totzke, P., & Zimmermann, M. (2021). HyperLTL Satisfiability is $Σ_1^1$-complete, HyperCTL* Satisfiability is $Σ_1^2$-complete. Retrieved from http://arxiv.org/abs/2105.04176v1

Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP (Conference Paper)

Totzke, P., Schewe, S., & Wojtczak, D. (2021). Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP. In Lecture Notes in Computer Science Vol. 12650 (pp. 427-447). Luxembourg: Springer Nature.

Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP (Journal article)

Mayr, R., Schewe, S., Totzke, P., & Wojtczak, D. (2021). Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP. FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2021, 12650, 427-447. doi:10.1007/978-3-030-71995-1_22

DOI: 10.1007/978-3-030-71995-1_22

Preface (Book)

Bell, P. C., Totzke, P., & Potapov, I. (2021). Preface (Vol. 13035 LNCS).

2020

Transience in Countable MDPs (Journal article)

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2020). Transience in Countable MDPs. Retrieved from http://arxiv.org/abs/2012.13739v3

Strategy Complexity of Parity Objectives in Countable MDPs (Conference Paper)

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2020). Strategy Complexity of Parity Objectives in Countable MDPs. In I. Konnov, & L. Kovács (Eds.), 31st International Conference on Concurrency Theory (CONCUR 2020) Vol. 171 (pp. 39:1-39:17). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CONCUR.2020.39

DOI: 10.4230/LIPIcs.CONCUR.2020.39

How to Play in Infinite MDPs (Invited Talk) (Conference Paper)

Kiefer, S., Mayr, R., Shirmohammadi, M., Totzke, P., & Wojtczak, D. (2020). How to Play in Infinite MDPs (Invited Talk). In A. Czumaj, A. Dawar, & E. Merelli (Eds.), 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) Vol. 168 (pp. 3:1-3:18). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2020.3

DOI: 10.4230/LIPIcs.ICALP.2020.3

Parametrized Universality Problems for One-Counter Nets (Conference Paper)

Almagor, S., Boker, U., Hofman, P., & Totzke, P. (2020). Parametrized Universality Problems for One-Counter Nets. Retrieved from http://arxiv.org/abs/2005.03435v2

DOI: 10.4230/LIPIcs.CONCUR.2020.47

Optimally Resilient Strategies in Pushdown Safety Games (Report)

Neider, D., Totzke, P., & Zimmermann, M. (n.d.). Optimally Resilient Strategies in Pushdown Safety Games. Retrieved from http://arxiv.org/abs/1912.04771v1

2019

Optimally Resilient Strategies in Pushdown Safety Games (Conference Paper)

Neider, D., Totzke, P., & Zimmermann, M. (2019). Optimally Resilient Strategies in Pushdown Safety Games. Retrieved from http://arxiv.org/abs/1912.04771v2

Controlling a Random Population is EXPTIME-hard (Internet publication)

Mascle, C., Shirmohammadi, M., & Totzke, P. (2019). Controlling a Random Population is EXPTIME-hard. Retrieved from http://arxiv.org/abs/1909.06420v1

Timed Basic Parallel Processes (Conference Paper)

Clemente, L., Hofman, P., & Totzke, P. (2019). Timed Basic Parallel Processes. Retrieved from http://arxiv.org/abs/1907.01240v2

DOI: 10.4230/LIPIcs.CONCUR.2019.15

Büchi Objectives in Countable MDPs (Conference Paper)

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2019). Büchi Objectives in Countable MDPs. Retrieved from http://arxiv.org/abs/1904.11573v2

DOI: 10.4230/LIPIcs.ICALP.2019.119

2018

Trace inclusion for one-counter nets revisited (Journal article)

Hofman, P., & Totzke, P. (2018). Trace inclusion for one-counter nets revisited. Theoretical Computer Science, 735, 50-63. doi:10.1016/j.tcs.2017.05.009

DOI: 10.1016/j.tcs.2017.05.009

Universal Safety for Timed Petri Nets is PSPACE-complete (Conference Paper)

Abdulla, P. A., Atig, M. F., Ciobanu, R., Mayr, R., & Totzke, P. (2018). Universal Safety for Timed Petri Nets is PSPACE-complete. Retrieved from http://arxiv.org/abs/1806.08170v1

Universal Safety for Timed Petri Nets is PSPACE-complete (Journal article)

Abdulla, P. A., Atig, M. F., Ciobanu, R., Mayr, R., & Totzke, P. (2018). Universal Safety for Timed Petri Nets is PSPACE-complete. CoRR, abs/1806.08170. Retrieved from http://arxiv.org/abs/1806.08170

2017

MDPs with energy-parity objectives (Conference Paper)

Mayr, R., Schewe, S., Totzke, P., & Wojtczak, D. (2017). MDPs with energy-parity objectives. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017 (pp. 1-12). Reykjavik, Iceland. doi:10.1109/LICS.2017.8005131

DOI: 10.1109/LICS.2017.8005131

Linear combinations of unordered data vectors (Conference Paper)

Leroux, J., Hofman, P., & Totzke, P. (2017). Linear combinations of unordered data vectors. In https://ieeexplore.ieee.org/document/8005065. Reykjavik, Iceland: IEEE Computer Society. doi:10.1109/LICS.2017.8005065

DOI: 10.1109/LICS.2017.8005065

MDPs with Energy-Parity Objectives (Journal article)

Mayr, R., Schewe, S., Totzke, P., & Wojtczak, D. (2017). MDPs with Energy-Parity Objectives. CoRR, abs/1701.02546. Retrieved from http://arxiv.org/abs/1701.02546

What Makes Petri Nets Harder to Verify: Stack or Data? (Conference Paper)

Lazić, R., & Totzke, P. (2017). What Makes Petri Nets Harder to Verify: Stack or Data?. In Unknown Conference (pp. 144-161). Springer International Publishing. doi:10.1007/978-3-319-51046-0_8

DOI: 10.1007/978-3-319-51046-0_8

2016

Linear Combinations of Unordered Data Vectors (Journal article)

Hofman, P., Leroux, J., & Totzke, P. (2016). Linear Combinations of Unordered Data Vectors. Retrieved from http://arxiv.org/abs/1610.01470v1

Simulation Problems Over One-Counter Nets (Journal article)

Hofman, P., Lasota, S., Mayr, R., & Totzke, P. (2016). Simulation Problems Over One-Counter Nets. Logical Methods in Computer Science, 12(1), 1. doi:10.2168/LMCS-12(1:6)2016

DOI: 10.2168/LMCS-12(1:6)2016

Branching-Time Model Checking Gap-Order Constraint Systems (Journal article)

Mayr, R., & Totzke, P. (2016). Branching-Time Model Checking Gap-Order Constraint Systems. FUNDAMENTA INFORMATICAE, 143(3-4), 339-353. doi:10.3233/FI-2016-1317

DOI: 10.3233/FI-2016-1317

A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One (Journal article)

Göller, S., Haase, C., Lazić, R., & Totzke, P. (2016). A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One. Retrieved from http://arxiv.org/abs/1602.05547v2

Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete (Conference Paper)

Englert, M., Lazic, R. S., & Totzke, P. (2016). Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete. In M. Grohe, E. Koskinen, & N. Shankar (Eds.), LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 477-484). ACM. doi:10.1145/2933575

DOI: 10.1145/2933575.2933577

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy (Conference Paper)

Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., & Sangiorgi, D. (Eds.) (2016). 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. In Unknown Conference Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-013-2

A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One (Journal article)

Göller, S., Haase, C., Lazic, R., & Totzke, P. (2016). A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One. CoRR, abs/1602.05547. Retrieved from http://arxiv.org/abs/1602.05547

Coverability Trees for Petri Nets with Unordered Data (Conference Paper)

Hofman, P., Lasota, S., Lazic, R., Leroux, J., Schmitz, S., & Totzke, P. (2016). Coverability Trees for Petri Nets with Unordered Data. In FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES (FOSSACS 2016) Vol. 9634 (pp. 445-461). doi:10.1007/978-3-662-49630-5_26

DOI: 10.1007/978-3-662-49630-5_26

Foundations of Software Science and Computation Structures (Conference Paper)

Jacobs, B., & Löding, C. (Eds.) (2016). Foundations of Software Science and Computation Structures. In . Springer Berlin Heidelberg. doi:10.1007/978-3-662-49630-5

DOI: 10.1007/978-3-662-49630-5

Linear Combinations of Unordered Data Vectors (Journal article)

Hofman, P., Leroux, J., & Totzke, P. (2016). Linear Combinations of Unordered Data Vectors. CoRR, abs/1610.01470. Retrieved from http://arxiv.org/abs/1610.01470

Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete (Journal article)

Englert, M., Lazic, R., & Totzke, P. (2016). Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete. CoRR, abs/1602.00477. Retrieved from http://arxiv.org/abs/1602.00477

2015

On Boundedness Problems for Pushdown Vector Addition Systems (Conference Paper)

Leroux, J., Sutre, G., & Totzke, P. (2015). On Boundedness Problems for Pushdown Vector Addition Systems. Retrieved from http://arxiv.org/abs/1507.07362v1

On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension (Journal article)

Leroux, J., Sutre, G., & Totzke, P. (2015). On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension. AUTOMATA, LANGUAGES, AND PROGRAMMING, PT II, 9135, 324-336. doi:10.1007/978-3-662-47666-6_26

DOI: 10.1007/978-3-662-47666-6_26

Automata, Languages, and Programming (Conference Paper)

Halldórsson, M. M., Iwama, K., Kobayashi, N., & Speckmann, B. (Eds.) (2015). Automata, Languages, and Programming. In . Springer Berlin Heidelberg. doi:10.1007/978-3-662-47666-6

DOI: 10.1007/978-3-662-47666-6

On Boundedness Problems for Pushdown Vector Addition Systems (Journal article)

Leroux, J., Sutre, G., & Totzke, P. (2015). On Boundedness Problems for Pushdown Vector Addition Systems. CoRR, abs/1507.07362. Retrieved from http://arxiv.org/abs/1507.07362

On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension (Journal article)

Leroux, J., Sutre, G., & Totzke, P. (2015). On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension. CoRR, abs/1503.04018. Retrieved from http://arxiv.org/abs/1503.04018

2014

Infinite-State Energy Games (Conference Paper)

Abdulla, P. A., Atig, M. F., Hofman, P., Mayr, R., Kumar, K. N., & Totzke, P. (2014). Infinite-State Energy Games. In PROCEEDINGS OF THE JOINT MEETING OF THE TWENTY-THIRD EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC (CSL) AND THE TWENTY-NINTH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS). doi:10.1145/2603088.2603100

DOI: 10.1145/2603088.2603100

Trace Inclusion for One-Counter Nets Revisited (Conference Paper)

Hofman, P., & Totzke, P. (2014). Trace Inclusion for One-Counter Nets Revisited. Retrieved from http://arxiv.org/abs/1404.5157v2

Inclusion problems for one-counter systems (Thesis / Dissertation)

Totzke, P. (2014). Inclusion problems for one-counter systems. (PhD Thesis, University of Edinburgh, UK). Retrieved from http://hdl.handle.net/1842/9646

Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ’14, Vienna, Austria, July 14 - 18, 2014 (Conference Paper)

Henzinger, T. A., & Miller, D. (Eds.) (2014). Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ’14, Vienna, Austria, July 14 - 18, 2014. In . ACM. Retrieved from http://dl.acm.org/citation.cfm?id=2603088

Trace Inclusion for One-Counter Nets Revisited (Journal article)

Hofman, P., & Totzke, P. (2014). Trace Inclusion for One-Counter Nets Revisited. CoRR, abs/1404.5157. Retrieved from http://arxiv.org/abs/1404.5157

2013

Simulation over one-counter nets is PSPACE-complete (Conference Paper)

Hofman, P., Lasota, S., Mayr, R., & Totzke, P. (2013). Simulation over one-counter nets is PSPACE-complete. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 24 (pp. 515-526). doi:10.4230/LIPIcs.FSTTCS.2013.515

DOI: 10.4230/LIPIcs.FSTTCS.2013.515

Decidability of Weak Simulation on One-Counter Nets (Conference Paper)

Hofman, P., Mayr, R., & Totzke, P. (2013). Decidability of Weak Simulation on One-counter Nets. In 2013 28TH ANNUAL IEEE/ACM SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS) (pp. 203-212). doi:10.1109/LICS.2013.26

DOI: 10.1109/LICS.2013.26

28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013 (Conference Paper)

28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013 (2013). IEEE Computer Society. Retrieved from http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6570844

Branching-Time Model Checking Gap-Order Constraint Systems (Conference Paper)

Mayr, R., & Totzke, P. (2013). Branching-Time Model Checking Gap-Order Constraint Systems. In REACHABILITY PROBLEMS Vol. 8169 (pp. 171-182). Retrieved from https://www.webofscience.com/

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India (Conference Paper)

Seth, A., & Vishnoi, N. K. (Eds.) (2013). IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India. In Unknown Conference Vol. 24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Retrieved from http://drops.dagstuhl.de/portals/extern/index.php?semnr=13018

2012

Approximating Weak Bisimilarity of Basic Parallel Processes (Conference Paper)

Hofman, P., & Totzke, P. (n.d.). Approximating Weak Bisimilarity of Basic Parallel Processes. In Electronic Proceedings in Theoretical Computer Science Vol. 89 (pp. 99-113). Open Publishing Association. doi:10.4204/eptcs.89.8

DOI: 10.4204/eptcs.89.8

2009

Multiset Pushdown Automata (Journal article)

Kudlek, M., Totzke, P., & Zetzsche, G. (2009). Multiset Pushdown Automata. Fundamenta Informaticae, 93(1-3), 221-233. doi:10.3233/fi-2009-0098

DOI: 10.3233/fi-2009-0098

Properties of Multiset Language Classes Defined by Multiset Pushdown Automata (Journal article)

Kudlek, M., Totzke, P., & Zetzsche, G. (2009). Properties of Multiset Language Classes Defined by Multiset Pushdown Automata. Fundamenta Informaticae, 93(1-3), 235-244. doi:10.3233/fi-2009-0099

DOI: 10.3233/fi-2009-0099

Multiset Pushdown Automata (Journal article)

Kudlek, M., Totzke, P., & Zetzsche, G. (2009). Multiset Pushdown Automata. FUNDAMENTA INFORMATICAE, 93(1-3), 221-233. doi:10.3233/FI-2009-98

DOI: 10.3233/FI-2009-98