On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic
Ugo Dal Lago, Guido Fiorillo, Paolo Pistone · 2026
Read On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic by Ugo Dal Lago, Guido Fiorillo, Paolo Pistone (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-27986.txt.
Introduction
Dal Lago, Fiorillo and Pistone tackle whether probabilistic higher-order programs stop with probability one, a question that cannot be decided in general. They translate the problem through the weighted relational semantics of linear logic into computing generating functions for the program. For a class extending affine recursion schemes with bounded exponentials, those functions are always algebraic. That gives a working test for stopping.
Catalog record
| CREATOR | Ugo Dal Lago, Guido Fiorillo, Paolo Pistone |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129505 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.27986
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic Ugo Dal Lago, Guido Fiorillo, Paolo Pistone Abstract The problem of determining whether a probabilistic program terminates almost surely (i.e. with probability one) is undecidable, and actually Π 2 0 \Pi^{0}_{2} -complete. For this reason, a growing literature has explored classes of programs for which this and related problems can be shown (semi-)decidable. In this work we consider the termination problem for the language of Probabilistic Higher-Order Recursion Schemes (PHORS). Using the weighted relational semantics of linear logic, we translate this problem into the computation of suitable generating functions associated with the program interpreted. This way, we establish the decidability of almost sure termination for a class of programs that extends Li et al.’s affine PHORS via a type discipline with bounded exponentials. To achieve this, we show that the generating functions for such programs are always algebraic, that is, solutions of polynomial equations, yielding an effective method to answer the termination problem. University of Bologna, Italy, and INRIA Sophia Antipolis, France [email protected]://orcid.org/0000-0001-9200-070XUniversité Claude Bernard Lyon 1, France [email protected] Université Claude Bernard Lyon 1, France [email protected]://orcid.org/0000-0003-4250-9051 {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003790.10003801¡/concept_id¿ ¡concept_desc¿Theory of computation Linear logic¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10011192¡/concept_id¿ ¡concept_desc¿Theory of computation Verification by model checking¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Linear logic ccs Theory of computation Verification by model checking keywords Probabilistic \lambda -calculus, linear logic, weighted relational model, algebraic power series † † runningauthor: U. Dal Lago, G. Fiorillo, P. Pistone † † copyright: Ugo Dal Lago, Guido Fiorillo, Paolo Pistone † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Probabilistic Higher-Order Verification Model checking is one of the most successful techniques for the verification of programs and systems [ 3 , 15 ] , and it has found applications in a wide range of areas, leading to the development of widely used tools such as SPIN [ 27 ] and PRISM [ 34 ] . While in its original formulation model checking focused on finite-state systems modeled by Kripke structures, its scope of application has gradually expanded over time, in directions that are often very different from one another. In this paper, we are particularly interested in two such directions. The first concerns the model checking of systems whose evolution is intrinsically probabilistic . Along this line of research, the literature has produced a rich body of results, both positive and negative, regarding the decidability and tractability of the underlying verification problem (see [ 5 ] for a recent survey). It is worth noting that when the property to be verified is reachability or termination (appropriately generalized to a probabilistic setting), verification may remain decidable even beyond the finite-state case, as in, for example, recursive Markov chains [ 19 ] or pushdown automata [ 17 ] . But there is also another generalization of model checking, likewise obtained by considering a broader class of systems than those traditionally studied, namely so-called higher-order model checking . It has been known for about twenty years that this problem is decidable when the underlying specification is an arbitrary MSO formula and the program is an higher-order recursion scheme (HORS, [ 40 , 41 ] ), a language equivalent to the simply-typed \lambda -calculus enriched with a fixpoint operator. Problems such as termination or reachability are therefore decidable for a broad class of programs encompassing higher-order types and recursion. These positive results have nonetheless revealed a certain degree of fragility: relatively minor extensions suffice to render the problem undecidable. What, then, happens when one considers model-checking problems for probabilistic and higher-order programs? Recently, Kobayashi et al. [ 32 ] have introduced probabilistic higher-order recursive schemes (PHORS), a probabilistic variant of HORS, which can be seen as the natural randomized variation on the theme of HORS. Unfortunately, verifying natural probabilistic counterparts of reachability and termination properties is in general a much more difficult task and is undecidable for PHORS, contrary to what happens for HORS and recursive Markov chains. For example, in a probabilistic setting, a natural property is almost sure termination (AST), that is, termination with probability 1. Now, while termination is the quintessential semi-decidable property for a Turing-complete language (and is even decidable for HORS), AST is \Pi^{0}_{2} -complete in Turing-complete probabilistic languages [ 28 ] , and its decidability fails for PHORS, already at order 2 [ 32 ] . For these reasons, the recent literature has focused on capturing sub-classes of PHORS for which AST and, possibly, the related positive almost sure termination (PAST) – the finiteness of the expected number of steps to termination – could be shown decidable, and thus possibly amenable to verification and model-checking techniques. Notably, while [ 32 ] established the decidability of AST for order-1 PHORS, Li et al. [ 38 ] established the decidability of both AST and PAST for the affine PHORS (styled PAHORS), i.e. the recursive programs which are allowed to use each of their inputs at most once during their reductions. Despite the aforementioned results, the nature of the problem remains poorly understood, and a precise assessment of its computational difficulty is still lacking. For instance, it is currently unknown whether the decidability problem for PHORS remains \Pi^{0}_{2} -complete, or whether it can, while being undecidable, be placed lower in the arithmetical hierarchy. Similarly, while different methods (like intersection types, game semantics or automata theory) have been applied to achieve decidability, a general approach encompassing all these results has not yet been identified. We therefore believe that it is important to investigate the nature of this problem in greater depth, which is the primary goal of this paper. Probabilistic Termination via Generating Functions Estimating the probability of termination of higher-order programs is hard, because it demands to count probabilities over a typically infinite set of reductions, a problem that remains difficult even when these reductions follow some well-defined recursive pattern. In fact, similar counting problems are common in the field of combinatorics, in which they are addressed by studying the algebraic and analytic properties of the corresponding generating functions , i.e. of the formal power series that are naturally associated with the sequence of numbers that one wishes to compute or estimate. A famous example is provided by the well-known Catalan numbers C_{n}=\frac{1}{n+1}\binom{2n}{n} , where C_{n} is the number of labeled binary trees with n nodes. This sequence induces the generating function c(x)=\sum_{n=0}^{\infty}C_{n}x^{n} , which can be characterized as the solution of a simple algebraic equation, namely xc(x)^{2}-c(x)+1=0 . From a polynomial equation like this it is possible to extract informatios about the generating function and the corresponding sequence that it would be otherwise very hard to compute directly. In our example, it allows us to deduce the closed expression c(x)=\frac{1-\sqrt{1-4x}}{2x} , hence providing a way to compute the values of c(x) effectively. Starting from Chomsky and Schützenberger’s seminal work [ 11 ] , generating functions have been widely applied in formal language theory. For example,