We report on ongoing research efforts aimed at exact asymptotic analysis of running time in probabilistic while loops. We focus on guarded-counter programs, translate them into probabilistic pushdown automata with global resets, and derive polynomial systems for their probability generating functions. After extracting dominant singularities, transfer theorems from analytic combinatorics yield coefficient asymptotics for runtime distributions.
Towards algebraic asymptotics for probabilistic loops / Boreale M., Collodi L., Pompa Di Gregorio A.. - ELETTRONICO. - 4269:(2026), pp. 301-308.
Towards algebraic asymptotics for probabilistic loops
Boreale M.
;Collodi L.;Pompa Di Gregorio A.
2026
Abstract
We report on ongoing research efforts aimed at exact asymptotic analysis of running time in probabilistic while loops. We focus on guarded-counter programs, translate them into probabilistic pushdown automata with global resets, and derive polynomial systems for their probability generating functions. After extracting dominant singularities, transfer theorems from analytic combinatorics yield coefficient asymptotics for runtime distributions.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
