EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Model Checking Probabilistic Operator Precedence Automata

Francesco Pontiggia, Ezio Bartocci, Michele Chiari

ACM Transactions on Computational Logic · 31.10.2026 · 27 (4) · 1-44

DOI: 10.1145/3822593 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 17.08.2026. Verfasst von Francesco Pontiggia und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 63 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Vienna Science and Technology Fund, WWTF project, EU Commission in the Horizon Europe research and innovation programme.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We address the problem of model checking context-free specifications for probabilistic pushdown automata, with applications in the verification of recursive probabilistic programs. Operator Precedence Languages (OPLs) are an expressive subclass of context-free languages suitable for model checking recursive programs. The derived Precedence Oriented Temporal Logic (POTL) can express fundamental OPL specifications such as pre/post-conditions and exception safety. We introduce probabilistic Operator Precedence Automata (pOPA), a class of probabilistic pushdown automata whose traces are OPLs, and study their model checking problem against POTL specifications. We identify a fragment of POTL, called POTLf \(\chi\) , for which we develop an exptime algorithm for qualitative probabilistic model checking, and an expspace algorithm for the quantitative variant. The algorithms rely on the property of separation of automata generated from POTLf \(\chi\) formulas. By the same property, the algorithms allow for model checking pOPA against Linear Temporal Logic (LTL) specifications. POTLf \(\chi\) is then the first context-free logic for which an optimal probabilistic model checking algorithm has been developed, matching its exptime lower bound in complexity. In comparison, the best-known algorithm for probabilistic model checking of CaRet, a prominent temporal logic based on Visibly Pushdown Languages (VPL), is doubly exponential.

Förderung

  • Vienna Science and Technology Fund
  • WWTF project
  • EU Commission in the Horizon Europe research and innovation programme

Zitieren

APA

Pontiggia, F., Bartocci, E., & Chiari, M. (2026). Model Checking Probabilistic Operator Precedence Automata. ACM Transactions on Computational Logic, 27(4), 1-44. https://doi.org/10.1145/3822593

Vancouver

Pontiggia F, Bartocci E, Chiari M. Model Checking Probabilistic Operator Precedence Automata. ACM Transactions on Computational Logic. 2026;27(4):1-44. doi:10.1145/3822593

BibTeX
@article{Pontiggia2026,
  author = {Pontiggia, Francesco and Bartocci, Ezio and Chiari, Michele},
  title = {Model Checking Probabilistic Operator Precedence Automata},
  journal = {ACM Transactions on Computational Logic},
  year = {2026},
  volume = {27},
  number = {4},
  pages = {1--44},
  doi = {10.1145/3822593}
}
Kostenlos starten →