Publications
2025
Resolving Nondeterminism by Chance
Paul, S., Purser, D., Schewe, S., Tang, Q., Totzke, P., & Yen, D. -D. (2025, August 26). Resolving Nondeterminism by Chance. In 36th International Conference on Concurrency Theory (CONCUR 2025). Aarhus, Denmark.
The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
Daviaud, L., Purser, D., & Tcheng, M. (n.d.). The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete). Logical Methods in Computer Science.
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 Leibniz International Proceedings in Informatics Lipics Vol. 311. 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 of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1-13). ACM. doi:10.1145/3661814.3662073
2023
History-Deterministic Vector Addition Systems
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
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 Unknown Conference (pp. 47-65). Springer Nature Switzerland. 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., Luca, F., Nieuwveld, J., Ouaknine, J., Purser, D., & Worrell, J. (2022). On the Skolem Problem and the Skolem Conjecture. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1-9). ACM. doi:10.1145/3531130.3533328
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Czerwiński, W., Lefaucheux, E., Mazowiecki, F., Purser, D., & Whiteland, M. (2022). The boundedness and zero isolation problems for weighted automata over nonnegative rationals. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1-13). ACM. 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
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), 1-25. doi:10.1145/3498727
The Big-O Problem
Chistikov, D., Kiefer, S., Murawski, A. S., & Purser, D. (2022). The Big-O Problem. Logical Methods in Computer Science, Volume 18, Issue 1. doi:10.46298/lmcs-18(1:40)2022
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 Unknown Conference (pp. 172-194). Springer International Publishing. 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 Unknown Conference (pp. 194-210). Springer International Publishing. doi:10.1007/978-3-030-01090-4_12