In this paper, we propose an inductive approach to prove positive almost sure termination of probabilistic rewriting under the innermost strategy. We extend to the probabilistic case a technique we proposed for termination of usual rewriting under strategies. The induction principle consists in assuming that terms smaller than the starting terms for an induction ordering are positively almost surely terminating. The proof is developed in generating proof trees, modelizing rewriting trees, in alternatively applying abstraction steps, expressing the application of the induction hypothesis, and narrowing steps, simulating the possible rewriting steps after abstraction. This technique can be fully automatized, in particular for rewrite systems on constants, very useful to modelize probabilistic protocols.  Categories and Subject Descriptors F.3.1 [LOGICS AND MEANINGS OF PROGRAMS Keywords Abstraction, Constraint, Narrowing, Probability, Termination Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.  Probabilistic rewriting has recently been introduced to modelize systems, where probabilistic and non-deterministic phenomena are combined [7] . A lot of models of systems, formalisms or techniques have already been enriched with probabilities, but most of them are restricted to finite state systems. Let us cite automata based models [11, 42] Rewriting allows for expressing complex relations on infinite sets of states in a finite way, provided they are countable. Rewriting also provides a nice programming paradigm: the rule-based formalism allows to easily write programs in a declarative way and the underlying algebraic semantics enables automatable or semi-automatable correctness proofs on the programs. Rule-based programming languages and environments are now currently used for any kind of application. Let In the context of probabilistic rewriting, the problem of termination naturally arises and in [4] , the notions of simple almost sure termination and positive almost sure (PAS in short) termination have been proposed, as well as a method based on interpretations on the reals to ensure the second property. The first termination notion expresses that the probability for a given rewriting derivation to terminate is 1; the second, stronger and more useful from a practical point of view, expresses that the mean length of the derivations from a term is finite. Then, in [5] , rewriting strategies have been considered, and sufficient criterions, still based on interpretations on the reals, have been given for PAS termination under strategies. Here, we try to go one step further. In the previously cited paper, the considered strategies defined themselves with probabilities, expressing the ratio of the selection of a rule w.r.t to another. We tackle here the PAS termination problem for position strategies, defined by the position of the redexes in the terms to be rewritten, using an inductive approach we proposed for proving termination of nonprobabilistic rewriting under the innermost [14] , the outermost [15] and local strategies [13] . In this paper, we adapt our inductive technique to the probabilistic case, investigate how it then works, and give a class of systems for which it is of interest. We focus here on the innermost strategy, consisting in always rewriting at the lowest possible positions. This strategy is widely used in programming. It is often used as a built-in mechanism in the evaluation of rule-based or functional languages. In addition, for non-overlapping or locally confluent overlay systems [21] , or systems satisfying critical peak conditions [22] , innermost termination is equivalent to standard termination (i.e. termination for standard rewriting, which consists in rewriting without any strategy). Note that as proved in [26] , leftmost innermost termination and innermost termination of rewriting are equivalent. A formalism has recently been proposed to extend the Constraint Handling Rule process with probabilistic capabilities applied to the rewrite rules themselves [16, 35, 36, 34, 37] . This is, to our knowledge, except the previously cited works on ELAN, Tom and Maude, the only attempt to formalize probabilistic transitions using rule based languages. Notice that these papers do not focus on techniques for proving termination of such systems. There are other works about termination with probabilities, but in the context of concurrent programs [40, 39] . They deal with almost sure termination, whereas we deal with positive almost sure termination. The basic idea of our approach is the following. We introduce the notion of innermost PAS (IPAS in short) termination for a term, and suppose, for every term t of a ground term algebra, that the terms smaller than t for an induction ordering are IPAS terminating. We then try to deduce that t is also IPAS terminating. The principle of our inductive method lies on a double mechanism allowing to generate proof trees, which represent, by a lifting mechanism, the rewriting trees of the ground terms: abstraction and narrowing. The paper is structured as follows. In Section 2, the background is presented. Section 3 is devoted to definitions of probabilistic rewriting. In Section 4, the material for our inductive technique in the probabilistic case is defined. Section 5 gives the algorithm generating proof trees and the IPAS termination result for finite proof trees. Finally, Section 6 presents a generalization to a given class of infinite proof trees. We assume that the reader is familiar with the basic definitions and notations of term rewriting given for instance in [1, 12, 41] . T (F, X ) is the set of terms built from a given finite set F of function symbols f having arity n ∈ N, and a set X of variables denoted x, y . . .. T (F) is the set of ground terms (without variables). The symbols of arity 0 are also terms called constants. Positions in a term are represented as sequences of integers. The empty sequence denotes the top position. Let p and p be two positions. The position p is said to be (a strict) prefix of p (and p suffix of p) if p = pλ, where λ is a (non-empty) sequence of integers. For a position p of a term t, we note t|p the subterm of t at position p, and t[s]p the term obtained in replacing by s the subterm at position p in t. A substitution is an assignment from X to T (F, X ), written σ = (x = t, . . . , y = u). It uniquely extends to an endomorphism of T (F, X ). The result of applying σ to a term t ∈ T (F, X ) is written σ(t) or σt. The domain of σ, denoted Dom(σ) is the finite subset of X such that σx = x. An instantiation or ground substitution is an assignment from X to T (F). Id denotes the identity substitution. The composition of substitutions σ1 followed by σ2 is denoted σ2σ1. A set R of rewrite rules or rewrite system (RS in short) on T (F, X ) is a set of pairs of terms of T (F, X ), denoted l → r, such that V ar(r) ⊆ V ar (l). Given a rewrite system R, a function symbol in F is called a constructor iff it does not occur in R at the top position of a left-hand side of rule, and is called a defined function symbol otherwise. The set of constructors of F for R is denoted CR, and the set of defined function symbols DR (R is omitted when there is no ambiguity). In this paper, we only consider finite sets of function symbols and of rewrite rules. The rewriting relation induced by R is denoted by → R (→ if there is no ambiguity on R), and defined by s → t iff there is a substitution σ and a position p in s such that s|p = σl for some rule l → r of R, and t = s [σr]p. This is written s → R p,l→r,σ t where p, l → r, σ or R may be omitted; s|p is called a redex. The innermost rewriting relation consists in always rewriting at the lowest possible positions. Let R be a rewrite system on T (F, X ). A term t is narrowed into t , at the non-variable position p, using the rewrite rule l → r of R and the substitution σ, when σ is a most general unifier of t|p and l, and t = σ(t[r]p). This is denoted t R p,l→r,σ t where p, l → r, σ or R may be omitted. It is always assumed that there is no variable in common between the rule and the term, i.e. that V ar(l)∩V ar(t) = ∅. An ordering on T (F, X ) is said to be noetherian iff there is no infinitely decreasing chain for this ordering. It is monotone iff for any pair of terms t, t of T (F, X ), For F and X finite, if is monotone and has the subterm property, then it is noetherian [27] . If, in addition, is stable under substitution (for any substitution σ, any pair of terms t, t ∈ T (F, X ), t t implies σt σt ), then it is called a simplification ordering. A RS R (innermost) terminates if and only if every (innermost) derivation of the rewriting relation induced by R is finite. For any term t of T (F), t (innermost) terminates if and only if every (innermost) rewriting derivation starting from t is finite. A σ-algebra on a set Ω is a set of subsets of Ω which contains the empty-set, and is stable by countable union and complementation. In particular, the set of subsets is a natural σ-algebra for any countable set. A measurable space (Ω, σ) is a set with a σ-algebra on it. A probability is a function P from a σ-algebra to [0, 1], which is countably additive, and such that P (Ω) = 1. A triplet (Ω, σ, P ) is called a probability space. For more details, see [23] . A stochastic sequence on a set A is a family (Xi) i∈N , of random variables defined on some fixed probability space (Ω, σ, P ) with values on A. [4] Given some countable set S, we note Dist(S) for the set of probability distributions on S: µ ∈ Dist(S) is a function S → [0, 1] that satisfies P i∈S µ(i) = 1. A probabilistic abstract reduction system (PARS) is a pair A = (A, →) consisting of a countable set A and a relation →⊂ A × Dist(A). A state a ∈ A with no µ such that a → µ is said terminal. 168 A history is a finite sequence a0a1 · · · an of elements of the state space A. It is non-terminal if an is as well. A history expresses the evolution of a PARS. The above definition assumes that strategies must be deterministic. A derivation of A is then a stochastic sequence where the non-deterministic choices are given by some policy φ, and the probabilistic choices are governed by the corresponding distributions. • and for all t ∈ A: If a derivation is such that πn = ⊥ for some n, then π n = ⊥ almost surely for all n ≥ n. Such a derivation is said to be terminating. If k is the greatest integer for which π k = ⊥, then π k is called a normal form (of π0). A nonterminating derivation is such that πn ∈ A (πn = ⊥) for all n. The following definition is generalized from [5] to a class of policies Φ. Definition 4 (PAS Termination). A PARS A = (A, →) will be said positively almost surely (PAS) terminating (under a class of strategies Φ) if for all policies φ (∈ Φ), for all states a ∈ A, the mean number of reduction steps (the mean length of the derivations) to reach a normal form starting from a under policy φ, denoted by T [a, φ], is finite. A probabilistic rewrite system is a finite set R of probabilistic rewrite rules. A probabilistic abstract reduction system (T (F, X ), →R) over the set of terms T (F, X ) is associated to a probabilistic rewrite system where →R is defined as follows. For example, with the probabilistic rewrite rule {f (x, y) → g(a) : 1/2|y : 1/2} whose right hand side denotes the distribution with value 1/2 on g(a) and value 1/2 on y, f (b, c) rewrites to g(a) with probability 1/2, to c with probability 1/2 and f (b, g(a)) rewrites to g(a) with probability 1. Innermost probabilistic rewriting consists in always applying the above definition at the lowest possible positions in the terms to be rewritten. A probabilistic rewrite system R is innermost positively almost surely (IPAS) terminating if the associated PARS is PAS terminating under the class ΦInn of policies φ corresponding to innermost rewriting derivations. A term t on which no rule of R applies is said to be in normal form for R. If such a term t is on a(n) (innermost) rewriting derivation of a term u, then t is called (innermost) normal form of u, and is noted u↓. To every rewriting derivation t0, t1, . . . , tn = t0↓ corresponds a derivation  π0, π1, . . . , πn, πn+1, . . . where πi = ⊥ for i > n. For proving that a probabilistic rewrite system on T (F) is IPAS terminating, we introduce a local notion of IPAS termination on terms, and prove this property for every term of T (F). For proving that a term t of T (F) is IPAS terminating, we proceed by induction on T (F) with a noetherian ordering , assuming the property for every t such that t t . To warrant non-emptiness of T (F), and a basis for the induction, we assume that F contains at least one constructor constant. The main intuition is to observe probabilistic rewriting derivations starting from a ground term t ∈ T (F) which is any instance of a pattern g(x1, . . . , xm) ∈ T (F, X ), for some defined function symbol g ∈ D, and variables x1, . . . , xm. Proving the property of IPAS termination on ground terms amounts to proving that every ground instance of the patterns g(x1, . . . , xm) is IPAS terminating. Rewriting derivations are simulated, using a lifting mechanism, by a proof tree developed from g(x1, . . . , xm) on T (F, X ), for every g ∈ D, by alternatively using two main concepts, namely narrowing and abstraction. More precisely, narrowing schematizes the rewriting possibilities of terms. Abstraction simulates the reduction of subterms in the derivations until these subterms become normal forms. It expresses the application of the induction hypothesis on these subterms: if they are IPAS terminating, with a mean number of reduction steps, they rewrite into a normal form. The schematization of ground rewriting derivations is achieved through constraints. The nodes of the developed proof trees are composed of a current term of T (F, X ), and a set of ground substitutions represented by a constraint progressively built along the successive abstraction and narrowing steps. Each node in an abstract tree schematizes a set of ground terms: all ground instances of the current term, that are solutions of the constraint. The constraint is in fact composed of two kinds of formulas: ordering constraints, set to warrant the validity of the inductive steps, and abstraction constraints combined 169 to narrowing substitutions, which effectively define the relevant sets of ground terms. For a term t of T (F, X ) occurring in a proof tree issued from a reference term t ref = g(x1, . . . , xm), • first, the ground instances of some subterms t|j of t (characterized by the constraint associated to t) are supposed to be IPAS terminating, by the induction hypothesis, if θt ref θt|j for the induction ordering and for every θ solution of the constraint associated to t. They are replaced in t by abstraction variables Xj representing respectively any of their normal forms, implicitely corresponding to one of the normal forms they have when rewriting under any policy φ ∈ ΦInn. Reasoning by induction allows us to only suppose the existence of the normal forms without explicitly computing them. If the ground instances of the resulting term are IPAS terminating (either if the induction hypothesis can be applied to them, or if they can be proved IPAS terminating by other means, we will present later), then the ground instances of the initial term are IPAS terminating. This technique is inspired from the one we proposed for proving innermost termination of non-probabilistic rewrite systems. We now introduce some concepts to formalize and automate it. The induction ordering is constrained along the proof by inequalities between terms that must be comparable, each time the induction hypothesis is used in the abstraction mechanism. This ordering is not defined a priori, but just has to verify inequalities of the form t > u1, . . . , um, accumulated along the proof, and which are called ordering constraints. Thus, for establishing the inductive termination proof, it is sufficient to decide whether ordering constraints are satisfiable. Satisfiability of a constraint conjunction C of this form is undecidable. But a sufficient condition for an ordering P on T (F, X ) to satisfy C is that t P t for every constraint t > t of C, and P is stable under substitution. Simplification orderings fulfill such a condition. So, in practice, it is sufficient to find a simplification ordering P such that t P t for every constraint t > t of C. The ordering P , defined on T (F, X ), can then be seen as an extension of the induction ordering on T (F). For convenience sake, P will also be written . Solving ordering constraints in finding simplification orderings is a well-known problem. The simplest way and an automatable way to proceed is to test simple existing orderings like the subterm ordering, the Recursive Path Ordering, or the Lexicographic Path Ordering. This is often sufficient for the constraints considered here: thanks to the power of induction, they are often simpler than for termination methods directly using ordering for orienting rewrite rules. If these simple orderings are not powerful enough, automatic solvers like Cime 1 can provide adequate polynomial orderings. To abstract a term t at positions i1, . . . , ip, where the t|j are supposed to have a normal form t|j ↓, we replace the t|j by abstraction variables Xj representing respectively any of their possible normal forms for any policy φ ∈ ΦInn. Let us define these special variables more formally.
termination in the context of term rewriting systems, Gnaedig REF developed a proof system for positive a.s.
Induction for positive almost sure termination
PPDP '07
Computer Science