Research outputs
2026
Representing One Letter Weighted Automata over the Tropical Semiring
Almagor, S., Jecker, I., Mazowiecki, F., Orlikowski, Ł., Purser, D., & Sinclair-Banks, H. (2026). Representing One Letter Weighted Automata over the Tropical Semiring. In Leibniz International Proceedings in Informatics Lipics Vol. 391. doi:10.4230/LIPIcs.CONCUR.2026.10
History-Constrained Systems
Kuijer, L. B., Purser, D., Sinclair-Banks, H., & Totzke, P. (2026). History-Constrained Systems. In Lecture Notes in Computer Science Vol. 16556 LNCS (pp. 541-558). doi:10.1007/978-3-032-26204-2_28
On the p-adic Skolem Problem
Bacik, P., Ouaknine, J., Purser, D., & Worrell, J. (2026). On the p-adic Skolem Problem. In Leibniz International Proceedings in Informatics Lipics Vol. 364. doi:10.4230/LIPIcs.STACS.2026.8
2025
Resolving Nondeterminism by Chance
Paul, S., Purser, D., Schewe, S., Tang, Q., Totzke, P., & Yen, D. -D. (2025). Resolving Nondeterminism by Chance. In 36TH INTERNATIONAL CONFERENCE ON CONCURRENCY THEORY, CONCUR 2025 Vol. 348 (pp. 22 pages). doi:10.4230/LIPIcs.CONCUR.2025.32
THE BIG-O PROBLEM FOR MAX-PLUS AUTOMATA IS DECIDABLE (PSPACE-COMPLETE)
Daviaud, L., Purser, D., & Tcheng, M. (2025). THE BIG-O PROBLEM FOR MAX-PLUS AUTOMATA IS DECIDABLE (PSPACE-COMPLETE). LOGICAL METHODS IN COMPUTER SCIENCE, 21(3), 35 pages. doi:10.46298/LMCS-21(3:3)2025
2024
Porous invariants for linear systems
Lefaucheux, E., Ouaknine, J., Purser, D., & Worrell, J. (2024). Porous invariants for linear systems. Formal Methods in System Design, 63(1-3), 235-271. doi:10.1007/s10703-024-00444-3
The Power of Counting Steps in Quantitative Games
Bose, S., Ibsen-Jensen, R., Purser, D., Totzke, P., & Vandenhove, P. (2024). The Power of Counting Steps in Quantitative Games. In 35TH INTERNATIONAL CONFERENCE ON CONCURRENCY THEORY, CONCUR 2024 Vol. 311 (pp. 18 pages). doi:10.4230/LIPIcs.CONCUR.2024.13
Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
Jecker, I., Mazowiecki, F., & Purser, D. (2024). Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata. In Proceedings Symposium on Logic in Computer Science. doi:10.1145/3661814.3662073
2023
History-Deterministic Vector Addition Systems
Bose, S., Purser, D., & Totzke, P. (2023). History-Deterministic Vector Addition Systems. In 34TH INTERNATIONAL CONFERENCE ON CONCURRENCY THEORY, CONCUR 2023 Vol. 279 (pp. 17 pages). doi:10.4230/LIPIcs.CONCUR.2023.18
The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
Daviaud, L., & Purser, D. (2023). The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete). In Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Boston, USA: IEEE.
Model Checking Linear Dynamical Systems under Floating-point Rounding
Lefaucheux, E., Ouaknine, J., Purser, D., & Sharifi, M. (2023). Model Checking Linear Dynamical Systems under Floating-point Rounding. In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics Vol. 13993 LNCS (pp. 47-65). doi:10.1007/978-3-031-30823-9_3
2022
Parameter Synthesis for Parametric Probabilistic Dynamical Systems and Prefix-Independent Specifications
Baier, C., Funke, F., Jantsch, S., Karimov, T., Lefaucheux, E., Ouaknine, J., . . . Worrell, J. (2022). Parameter Synthesis for Parametric Probabilistic Dynamical Systems and Prefix-Independent Specifications. In Leibniz International Proceedings in Informatics Lipics Vol. 243. doi:10.4230/LIPIcs.CONCUR.2022.10
On the Skolem Problem and the Skolem Conjecture
Lipton, R. J., Luca, F., Nieuwveld, J., Ouaknine, J., Purser, D., & Worrell, J. (2022). On the Skolem Problem and the Skolem Conjecture. In Proceedings Symposium on Logic in Computer Science. doi:10.1145/3531130.3533328
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Czerwinski, W., Lefaucheux, E., Mazowiecki, F., Purser, D., & Whiteland, M. A. (2022). The boundedness and zero isolation problems for weighted automata over nonnegative rationals. In Proceedings Symposium on Logic in Computer Science. doi:10.1145/3531130.3533336
Skolem Meets Schanuel
Bilu, Y., Luca, F., Nieuwveld, J., Ouaknine, J., Purser, D., & Worrell, J. (2022). Skolem Meets Schanuel. In Leibniz International Proceedings in Informatics Lipics Vol. 241. doi:10.4230/LIPIcs.MFCS.2022.20
THE BIG-O PROBLEM
Chistikov, D., Kiefer, S., Murawski, A. S., & Purser, D. (2022). THE BIG-O PROBLEM. Logical Methods in Computer Science, 18(1), 40-50. doi:10.46298/LMCS-18(1:40)2022
What s Decidable about Linear Loops
Karimov, T., Lefaucheux, E., Ouaknine, J., Purser, D., Varonka, A., Whiteland, M. A., & Worrell, J. (2022). What s Decidable about Linear Loops. Proceedings of the ACM on Programming Languages, 6(POPL). doi:10.1145/3498727
2021
The Orbit Problem for Parametric Linear Dynamical Systems
Baier, C., Jantsch, S., Lefaucheux, E., Ouaknine, J., Whiteland, M. A., Funke, F., . . . Worrell, J. (2021). The Orbit Problem for Parametric Linear Dynamical Systems. In Leibniz International Proceedings in Informatics Lipics Vol. 203. doi:10.4230/LIPIcs.CONCUR.2021.28
Porous Invariants
Lefaucheux, E., Ouaknine, J., Purser, D., & Worrell, J. (2021). Porous Invariants. In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics Vol. 12760 LNCS (pp. 172-194). doi:10.1007/978-3-030-81688-9_8
2020
Reachability in dynamical systems with rounding
Baier, C., Funke, F., Jantsch, S., Karimov, T., Lefaucheux, E., Ouaknine, J., . . . Whiteland, M. A. (2020). Reachability in dynamical systems with rounding. In Leibniz International Proceedings in Informatics Lipics Vol. 182. doi:10.4230/LIPIcs.FSTTCS.2020.36
The big-O problem for labelled Markov chains and weighted automata
Chistikov, D., Kiefer, S., Murawski, A. S., & Purser, D. (2020). The big-O problem for labelled Markov chains and weighted automata. In Leibniz International Proceedings in Informatics Lipics Vol. 171 (pp. 411-4119). doi:10.4230/LIPIcs.CONCUR.2020.41
The Complexity of Verifying Loop-Free Programs as Differentially Private.
Gaboardi, M., Nissim, K., & Purser, D. (2020). The complexity of verifying loop-free programs as differentially private. In Leibniz International Proceedings in Informatics Lipics Vol. 168. doi:10.4230/LIPIcs.ICALP.2020.129
2019
Structural liveness of Petri nets is ExpSpace-hard and decidable
Jančar, P., & Purser, D. (2019). Structural liveness of Petri nets is ExpSpace-hard and decidable. Acta Informatica, 56(6), 537-552. doi:10.1007/s00236-019-00338-6
Asymmetric distances for approximate differential privacy
Chistikov, D., Murawski, A. S., & Purser, D. (2019). Asymmetric distances for approximate differential privacy. In Leibniz International Proceedings in Informatics Lipics Vol. 140. doi:10.4230/LIPIcs.CONCUR.2019.10
2018
Bisimilarity Distances for Approximate Differential Privacy
Chistikov, D., Murawski, A. S., & Purser, D. (2018). Bisimilarity Distances for Approximate Differential Privacy. In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics Vol. 11138 LNCS (pp. 194-210). doi:10.1007/978-3-030-01090-4_12