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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Probabilistic pushdown automata (pPDA) are a natural operational model for avariety of recursive discrete stochastic processes. In this paper, we studycertificates - succinct and easily verifiable proofs - for upper and lowerbounds on various quantitative properties of a given pPDA. We reveal anintimate, yet surprisingly simple connection between the existence of suchcertificates and the expected time to termination of the pPDA at hand. This isestablished by showing that certain intrinsic properties, like the spectralradius of the Jacobian of the pPDA's underlying polynomial equation system, aredirectly related to expected runtimes. As a consequence, we obtain that therealways exist easy-to-check proofs for positive almost-sure termination: does apPDA terminate in finite expected time?

On Certificates, Expected Runtimes, and Termination in Probabilistic Pushdown Automata