English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Probabilistic programs extend classical imperative programs with real-valuedrandom variables and random branching. The most basic liveness property forsuch programs is the termination property. The qualitative (aka almost-sure)termination problem given a probabilistic program asks whether the programterminates with probability 1. While ranking functions provide a sound andcomplete method for non-probabilistic programs, the extension of them toprobabilistic programs is achieved via ranking supermartingales (RSMs). Whiledeep theoretical results have been established about RSMs, their application toprobabilistic programs with nondeterminism has been limited only to academicexamples. For non-probabilistic programs, lexicographic ranking functionsprovide a compositional and practical approach for termination analysis ofreal-world programs. In this work we introduce lexicographic RSMs and show thatthey present a sound method for almost-sure termination of probabilisticprograms with nondeterminism. We show that lexicographic RSMs provide a toolfor compositional reasoning about almost sure termination, and forprobabilistic programs with linear arithmetic they can be synthesizedefficiently (in polynomial time). We also show that with additionalrestrictions even asymptotic bounds on expected termination time can beobtained through lexicographic RSMs. Finally, we present experimental resultson abstractions of real-world programs to demonstrate the effectiveness of ourapproach.

Lexicographic Ranking Supermartingales: An Efficient Approach to Termination of Probabilistic Programs