Mining Statistically Likely k-Reachable States in Probabilistic Programs

Ray, Arnab; Trivedi, Nitesh; Banerjee, Ansuman; Chakraborty, Sourav; Ghosh, Arijit; Roy, Subhajit

doi:10.24963/ijcai.2026/712

Mining Statistically Likely k-Reachable States in Probabilistic Programs

Arnab Ray, Nitesh Trivedi, Ansuman Banerjee, Sourav Chakraborty, Arijit Ghosh, Subhajit Roy

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 6398-6406.

https://doi.org/10.24963/ijcai.2026/712

Keywords

Uncertainty in AI: Probabilistic programming

Abstract

We propose the notion of statistically likely k-step reachable set in probabilistic programs, a statistically robust notion for high-probability k-step reachable program states. We design an inductive algorithm to capture this set as a symbolic representation in propositional logic for Boolean probabilistic programs. Our methodology iteratively learns a symbolic formula for the statistically likely k-step reachable set that involves (a) learning an initial symbolic candidate via decision tree learning, (b) collecting positive and negative counterexamples via forward and backward verification checks, and (c) refining the current candidate via a sequence of prune and split moves on the decision tree. We demonstrate that the statistically likely k-step reachable set can reveal interesting properties about programs by studying probabilistic programs from the literature.

Arnab Ray, Nitesh Trivedi, Ansuman Banerjee, Sourav Chakraborty, Arijit Ghosh, and Subhajit Roy. 2026. Mining Statistically Likely k-Reachable States in Probabilistic Programs. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 6398–6406. https://doi.org/10.24963/ijcai.2026/712

@inproceedings{ijcai2026p712,
  title     = {Mining Statistically Likely k-Reachable States in Probabilistic Programs},
  author    = {Ray, Arnab and Trivedi, Nitesh and Banerjee, Ansuman and Chakraborty, Sourav and Ghosh, Arijit and Roy, Subhajit},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {6398--6406},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/712},
  url       = {https://doi.org/10.24963/ijcai.2026/712},
}

TY  - CPAPER
TI  - Mining Statistically Likely k-Reachable States in Probabilistic Programs
AU  - Ray, Arnab
AU  - Trivedi, Nitesh
AU  - Banerjee, Ansuman
AU  - Chakraborty, Sourav
AU  - Ghosh, Arijit
AU  - Roy, Subhajit
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 6398
EP  - 6406
DO  - 10.24963/ijcai.2026/712
UR  - https://doi.org/10.24963/ijcai.2026/712
ER  -