Paper Accepted by CAV 2025

Our paper has been accepted for presentation at CAV 2025.

Our paper titled “On the Almost-Sure Termination of Probabilistic Counter Programs” by Sergei Novozhilov, Mingqi Yang, Mingshuai Chen, Zhiyang Li, and Jianwei Yin has been accepted for presentation at CAV 2025 – the 37th International Conference on Computer Aided Verification, at Zagreb, Croatia. This paper introduces $k$-d PCPs – the class of probabilistic counter programs with $k \in \mathbb{N}$ counter variables inducing possibly infinite-state Markov chains. We show that the universal (positive) almost-sure termination problem is undecidable for $k$-d PCPs in general, yet decidable for $1$-d PCPs.