Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Inference rules, pattern footprints, and resource boundedness

Definition
MoserSchneckenreither_Typing

by kmehltretter82 · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

amortized-analysiscomplexityresource-analysisterm-rewritingtype-systems

The footprint judgement has application, composition, sharing, and variable rules; the full judgement additionally has all four source weakening rules. Contexts are finite partial maps represented up to permutation. Freshness, disjoint context domains, and linearity in composition are explicit. A substitution is consistent with a context when its domain covers the context and each substituted ground value has the assigned annotation, with its typing cost existentially quantified. The potential freed by a pattern is specified by an explicit linearisation, footprint derivations for its arguments, and summation of annotations for copies of each original variable. A rule is resource bounded when the right-hand side is derivable within the root cost plus freed potential, less its charge. The budget is expressed by an equality with a nonnegative residual cost, avoiding truncated subtraction. Strict rules cost one and weak rules zero; the optional cost-free mode charges neither. Resource boundedness is syntactic and contains no assumption about operational potential decrease.

Definition code
import Definitions.Def_MoserSchneckenreither_Annotations

/-!
Figure 2 and Definitions 4–6 of Moser–Schneckenreither, arXiv:1811.09071v1, pp. 9–11.
The footprint uses app, comp, share and var; full typing also admits the four weakenings.
Contexts are finite partial maps represented up to permutation. Freshness, disjointness,
and the linearity condition on comp are explicit.
-/

namespace MoserSchneckenreither

inductive Mode where
  | footprint
  | full

variable {sig : Signature} {P : Problem sig}

def flatContext {n : ℕ} (xs : Fin n → ℕ) (ps : Fin n → Annotation) : Context :=
  List.ofFn fun i ↦ (xs i, ps i)

/-- The source inference rules. No operational cost inequality is a constructor of this relation. -/
inductive Typing (F : AnnotatedSignature P) :
    Mode → Context → ℚ≥0 → Term sig → Annotation → Prop
  | app (mode : Mode) (f : Symbol sig) (a : Declaration (sig.arity f))
      (ha : F.declarations f a) (xs : Fin (sig.arity f) → ℕ)
      (hx : Function.Injective xs) :
      Typing F mode (flatContext xs a.inputs) a.cost (.app f fun i ↦ .var (xs i)) a.output
  | var (mode : Mode) (x : ℕ) (q : Annotation) :
      Typing F mode [(x, q)] 0 (.var x) q
  | comp {mode : Mode} (f : Symbol sig) (ts : Fin (sig.arity f) → Term sig)
      (xs : Fin (sig.arity f) → ℕ) (ps : Fin (sig.arity f) → Annotation)
      (Γs : Fin (sig.arity f) → Context) (ks : Fin (sig.arity f) → ℚ≥0)
      (k₀ : ℚ≥0) (q : Annotation) (hx : Function.Injective xs)
      (hfresh : ∀ i j, xs i ∉ (Γs j).keys)
      (hdisjoint : ∀ i j, i ≠ j → ∀ x ∈ (Γs i).keys, x ∉ (Γs j).keys)
      (hlinear : (Term.app f ts).Linear)
      (hhead : Typing F mode (flatContext xs ps) k₀ (.app f fun i ↦ .var (xs i)) q)
      (hargs : ∀ i, Typing F mode (Γs i) (ks i) (ts i) (ps i)) :
      Typing F mode (List.ofFn Γs).flatten (k₀ + (List.ofFn ks).sum) (.app f ts) q
  | share {mode : Mode} (Γ : Context) (x y z : ℕ) (p₁ p₂ p q : Annotation)
      (t : Term sig) (k : ℚ≥0) (hshare : Shares p p₁ p₂)
      (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z)
      (hx : x ∉ Γ.keys) (hy : y ∉ Γ.keys) (hz : z ∉ Γ.keys)
      (h : Typing F mode (Γ ++ [(x, p₁), (y, p₂)]) k t q) :
      Typing F mode (Γ ++ [(z, p)]) k
        (t.rename fun w ↦ if w = x ∨ w = y then z else w) q
  | perm {mode : Mode} {Γ Δ : Context} {k : ℚ≥0} {t : Term sig} {q : Annotation}
      (hperm : Γ.Perm Δ) (h : Typing F mode Γ k t q) : Typing F mode Δ k t q
  | w1 {Γ : Context} {k k' : ℚ≥0} {t : Term sig} {q : Annotation}
      (h : Typing F .full Γ k t q) (hk : k ≤ k') : Typing F .full Γ k' t q
  | w2 (Γ : Context) (x : ℕ) (p r q : Annotation) (k : ℚ≥0) (t : Term sig)
      (h : Typing F .full (Γ ++ [(x, r)]) k t q) (hr : r ≤ p) :
      Typing F .full (Γ ++ [(x, p)]) k t q
  | w3 {Γ : Context} {k : ℚ≥0} {t : Term sig} {q s : Annotation}
      (h : Typing F .full Γ k t s) (hq : q ≤ s) : Typing F .full Γ k t q
  | w4 (Γ : Context) (x : ℕ) (p q : Annotation) (k : ℚ≥0) (t : Term sig)
      (hx : x ∉ Γ.keys) (h : Typing F .full Γ k t q) :
      Typing F .full (Γ ++ [(x, p)]) k t q

/-- Compatibility of a normalised substitution with each context annotation, ignoring its cost. -/
def Consistent (F : AnnotatedSignature P) (σ : Substitution sig) (Γ : Context) : Prop :=
  Γ.Valid ∧ ∀ x q, (x, q) ∈ Γ → x ∈ σ.domain ∧
    ∃ k, Typing F .full [] k (σ.apply x) q

/-- Definition 5: linearise the argument patterns, derive their footprints, then merge renamings. -/
def Frees (F : AnnotatedSignature P) {n : ℕ} (ts : Fin n → Term sig)
    (ps : Fin n → Annotation) (Γ : Context) (ℓ : ℚ≥0) : Prop :=
  ∃ (us : Fin n → Term sig) (ρ : ℕ → ℕ) (Γs : Fin n → Context) (ks : Fin n → ℚ≥0),
    ((List.ofFn fun i ↦ (us i).vars).flatten).Nodup ∧
    (∀ i, (us i).rename ρ = ts i) ∧
    (∀ i, (Γs i).keys.Perm (us i).vars ∧ Typing F .footprint (Γs i) (ks i) (us i) (ps i)) ∧
    Γ = Context.renameMerge (List.ofFn Γs).flatten ρ ∧ ℓ = (List.ofFn ks).sum

/-- The syntactic budget condition for one rule and one annotation of its root. -/
def RuleBounded (F : AnnotatedSignature P) (r : Rule sig) (charge : ℚ≥0) : Prop :=
  ∀ a, F.declarations r.head a → ∃ Γ ℓ k,
    Frees F r.args a.inputs Γ ℓ ∧ a.cost + ℓ = charge + k ∧
    Typing F .full Γ k r.rhs a.output

/-- Definition 6, with cost-free boundedness selected by `countStrict = false`. -/
def ResourceBounded (F : AnnotatedSignature P) (countStrict : Bool := true) : Prop :=
  (∀ r ∈ P.strict, RuleBounded F r (if countStrict then 1 else 0)) ∧
  (∀ r ∈ P.weak, RuleBounded F r 0)

end MoserSchneckenreither
Source
Georg Moser and Manuel Schneckenreither, Automated amortised resource analysis for term rewrite systems, Science of Computer Programming 185 (2020), article 102306, https://doi.org/10.1016/j.scico.2019.102306. Section 5, pp. 8–10, Figure 4 and Definitions 4–6.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex)

Signature. The underlying signature consists of a natural number NNN, symbols 0,…,N−10,\ldots,N-10,…,N−1, an arity a(f)∈Na(f)\in\mathbb Na(f)∈N for each symbol fff, and a nonempty designated set CCC of constructor symbols. At least one symbol has arity zero; that symbol is not required to belong to CCC. In particular the symbol set is nonempty, and individual symbols may have arity zero.

Terms, variables, and renaming. Terms are finite expressions formed from variables indexed by N\mathbb NN and applications f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​). The list V(t)V(t)V(t) of variable occurrences is [x][x][x] for the variable xxx and the concatenation, in argument order, of the lists V(ti)V(t_i)V(ti​) for an application; repetitions are retained. A term is ground when this list is empty and linear when this list has no repeated entry. For a total map θ:N→{terms}\theta:\mathbb N\to\{\text{terms}\}θ:N→{terms}, t[θ]t[\theta]t[θ] replaces every variable xxx in ttt by θ(x)\theta(x)θ(x), recursively through applications; this does not recursively apply θ\thetaθ inside its replacement terms. A renaming by a total map ρ:N→N\rho:\mathbb N\to\mathbb Nρ:N→N is the substitution sending xxx to the variable ρ(x)\rho(x)ρ(x). The symbols occurring in a term are all its application labels, including those below its root.

Rules and problems. A rule rrr consists of a head symbol fr∉Cf_r\notin Cfr​∈/C, exactly a(fr)a(f_r)a(fr​) argument terms sr,is_{r,i}sr,i​, and a right-hand term uru_rur​, with the requirement that each variable occurring in uru_rur​ occurs somewhere in fr(sr,0,…,sr,a(fr)−1)f_r(s_{r,0},\ldots,s_{r,a(f_r)-1})fr​(sr,0​,…,sr,a(fr​)−1​). Its left-hand term is this application. The arguments are not required to be constructor terms or to contain distinct variables. A problem PPP consists of finite lists RRR and WWW of such rules, called strict and weak respectively, and its combined rule list is RRR followed by WWW. Either list may be empty, may repeat rules, and may overlap the other list. Let LLL be the set of symbols that either belong to CCC or occur anywhere inside an argument sr,is_{r,i}sr,i​ of a rule in either list.

Annotations and declarations. An annotation is a finitely supported function N→Q≥0\mathbb N\to\mathbb Q_{\ge0}N→Q≥0​; addition, multiplication by a nonnegative rational scalar, and comparison are pointwise. The zero annotation is permitted. An arity-nnn declaration is a triple ((pi)i<n,κ,q)((p_i)_{i<n},\kappa,q)((pi​)i<n​,κ,q) consisting of nnn input annotations, a cost κ∈Q≥0\kappa\in\mathbb Q_{\ge0}κ∈Q≥0​, and an output annotation qqq; n=0n=0n=0 is permitted.

Annotated signature. For the given signature and problem, FFF supplies, for each symbol fff, a nonempty collection Df\mathcal D_fDf​ of arity-a(f)a(f)a(f) declarations, and, for every output annotation qqq, input annotations If(q)iI_f(q)_iIf​(q)i​ for i<a(f)i<a(f)i<a(f) and a cost cf(q)∈Q≥0c_f(q)\in\mathbb Q_{\ge0}cf​(q)∈Q≥0​. For every f∈Lf\in Lf∈L and every annotation qqq, the declaration ((If(q)i)i<a(f),cf(q),q)((I_f(q)_i)_{i<a(f)},c_f(q),q)((If​(q)i​)i<a(f)​,cf​(q),q) belongs to Df\mathcal D_fDf​; every declaration ((pi),κ,q)∈Df((p_i),\kappa,q)\in\mathcal D_f((pi​),κ,q)∈Df​ for such an fff has pi=If(q)ip_i=I_f(q)_ipi​=If​(q)i​ for all iii and κ=cf(q)\kappa=c_f(q)κ=cf​(q). For every f∈Lf\in Lf∈L and annotations p,qp,qp,q, one has cf(p+q)=cf(p)+cf(q)c_f(p+q)=c_f(p)+c_f(q)cf​(p+q)=cf​(p)+cf​(q) and, for every i<a(f)i<a(f)i<a(f), If(p+q)i=If(p)i+If(q)iI_f(p+q)_i=I_f(p)_i+I_f(q)_iIf​(p+q)i​=If​(p)i​+If​(q)i​. For every f∈Lf\in Lf∈L, scalar λ∈Q≥0\lambda\in\mathbb Q_{\ge0}λ∈Q≥0​, and annotation qqq, one has cf(λq)=λcf(q)c_f(\lambda q)=\lambda c_f(q)cf​(λq)=λcf​(q) and, for every i<a(f)i<a(f)i<a(f), If(λq)i=λIf(q)iI_f(\lambda q)_i=\lambda I_f(q)_iIf​(λq)i​=λIf​(q)i​. The cost equations apply also to nullary symbols. No corresponding uniqueness, addition, or scaling condition is imposed on symbols outside LLL, although their declaration collections must still be nonempty and their functions If,cfI_f,c_fIf​,cf​ are still supplied.

Contexts. A context is a finite ordered list of pairs (x,q)(x,q)(x,q) with x∈Nx\in\mathbb Nx∈N and qqq an annotation. Its key list is the list of first components, retaining order and repetitions; it is valid exactly when this list has no repeated entry. The empty context is permitted, and arbitrary contexts are not presumed valid. Concatenation of contexts is list concatenation, and a permutation of a context preserves its entries with their multiplicities. All sums over empty lists or empty argument families are zero.

Finite-domain substitutions. A substitution σ\sigmaσ consists of a finite domain Dσ⊆ND_\sigma\subseteq\mathbb NDσ​⊆N and a total assignment Aσ:N→{terms}A_\sigma:\mathbb N\to\{\text{terms}\}Aσ​:N→{terms}. Its effective action is σˉ(x)=Aσ(x)\bar\sigma(x)=A_\sigma(x)σˉ(x)=Aσ​(x) when x∈Dσx\in D_\sigmax∈Dσ​ and the variable xxx otherwise. Write tσt\sigmatσ for t[σˉ]t[\bar\sigma]t[σˉ]. No requirement is imposed on the assignment outside DσD_\sigmaDσ​, and the domain may be empty.

Mode. There are exactly two modes, called footprint and full.

Flat context. For every natural number nnn, every family of variable names (xi)i<n(x_i)_{i<n}(xi​)i<n​, and every family of annotations (pi)i<n(p_i)_{i<n}(pi​)i<n​, the flat context is the ordered list [(x0,p0),…,(xn−1,pn−1)][(x_0,p_0),\ldots,(x_{n-1},p_{n-1})][(x0​,p0​),…,(xn−1​,pn−1​)]. This definition places no distinctness requirement on the names. For n=0n=0n=0 it is the empty list.

Typing. For the given FFF, write Γ⊢mkt:q\Gamma\vdash_m^k t:qΓ⊢mk​t:q for the least family of relations with mode mmm equal to footprint or full, context Γ\GammaΓ, cost k∈Q≥0k\in\mathbb Q_{\ge0}k∈Q≥0​, term ttt, and annotation qqq, generated by the following rules. All cost variables in these rules are nonnegative rationals, all annotation variables are finitely supported nonnegative-rational sequences, and all variable names are natural numbers. In either mode, for every symbol fff, declaration ((pi),κ,q)∈Df((p_i),\kappa,q)\in\mathcal D_f((pi​),κ,q)∈Df​, and pairwise distinct names xix_ixi​ indexed by i<a(f)i<a(f)i<a(f), the ordered context [(xi,pi)]i<a(f)[(x_i,p_i)]_{i<a(f)}[(xi​,pi​)]i<a(f)​ types f(x0,…,xa(f)−1)f(x_0,\ldots,x_{a(f)-1})f(x0​,…,xa(f)−1​) at cost κ\kappaκ with output qqq; also [(x,q)]⊢m0x:q[(x,q)]\vdash_m^0 x:q[(x,q)]⊢m0​x:q for every x,qx,qx,q. For composition, choose a symbol fff, terms tit_iti​, names xix_ixi​, annotations pip_ipi​, contexts Γi\Gamma_iΓi​, and costs bib_ibi​ for i<a(f)i<a(f)i<a(f), and a cost κ\kappaκ and output annotation qqq. If the xix_ixi​ are pairwise distinct and each xix_ixi​ is absent from every key list of every Γj\Gamma_jΓj​, contexts Γi,Γj\Gamma_i,\Gamma_jΓi​,Γj​ at distinct indices have disjoint sets of keys, the concatenation of the variable-occurrence lists of the tit_iti​ has no repetitions, [(xi,pi)]i<a(f)⊢mκf(x0,…,xa(f)−1):q[(x_i,p_i)]_{i<a(f)}\vdash_m^{\kappa}f(x_0,\ldots,x_{a(f)-1}):q[(xi​,pi​)]i<a(f)​⊢mκ​f(x0​,…,xa(f)−1​):q, and Γi⊢mbiti:pi\Gamma_i\vdash_m^{b_i}t_i:p_iΓi​⊢mbi​​ti​:pi​ for every iii, then the concatenation Γ0+ ⁣ ⁣+⋯+ ⁣ ⁣+Γa(f)−1\Gamma_0\mathbin{+\!\!+}\cdots\mathbin{+\!\!+}\Gamma_{a(f)-1}Γ0​++⋯++Γa(f)−1​ types f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) in the same mode at cost κ+∑i<a(f)bi\kappa+\sum_{i<a(f)}b_iκ+∑i<a(f)​bi​ with output qqq. For sharing, for every context Γ\GammaΓ, pairwise distinct names x,y,zx,y,zx,y,z all absent from its keys, annotations p1,p2,p,qp_1,p_2,p,qp1​,p2​,p,q with p1+p2=pp_1+p_2=pp1​+p2​=p, term ttt, and cost kkk, a judgment Γ+ ⁣ ⁣+[(x,p1),(y,p2)]⊢mkt:q\Gamma\mathbin{+\!\!+}[(x,p_1),(y,p_2)]\vdash_m^k t:qΓ++[(x,p1​),(y,p2​)]⊢mk​t:q gives Γ+ ⁣ ⁣+[(z,p)]⊢mkt′:q\Gamma\mathbin{+\!\!+}[(z,p)]\vdash_m^k t':qΓ++[(z,p)]⊢mk​t′:q, where t′t't′ replaces every variable named xxx or yyy by zzz and leaves all other names unchanged. In either mode, any permutation of the context preserves a judgment with the same cost, term, and output. In full mode there are four additional rules: from Γ⊢fullkt:q\Gamma\vdash_{\mathrm{full}}^k t:qΓ⊢fullk​t:q and k≤k′k\le k'k≤k′ obtain Γ⊢fullk′t:q\Gamma\vdash_{\mathrm{full}}^{k'}t:qΓ⊢fullk′​t:q; from Γ+ ⁣ ⁣+[(x,r)]⊢fullkt:q\Gamma\mathbin{+\!\!+}[(x,r)]\vdash_{\mathrm{full}}^k t:qΓ++[(x,r)]⊢fullk​t:q and r≤pr\le pr≤p obtain Γ+ ⁣ ⁣+[(x,p)]⊢fullkt:q\Gamma\mathbin{+\!\!+}[(x,p)]\vdash_{\mathrm{full}}^k t:qΓ++[(x,p)]⊢fullk​t:q, with no extra freshness premise in this rule; from Γ⊢fullkt:s\Gamma\vdash_{\mathrm{full}}^k t:sΓ⊢fullk​t:s and q≤sq\le sq≤s obtain Γ⊢fullkt:q\Gamma\vdash_{\mathrm{full}}^k t:qΓ⊢fullk​t:q; and from Γ⊢fullkt:q\Gamma\vdash_{\mathrm{full}}^k t:qΓ⊢fullk​t:q and a name xxx absent from Γ\GammaΓ's keys obtain Γ+ ⁣ ⁣+[(x,p)]⊢fullkt:q\Gamma\mathbin{+\!\!+}[(x,p)]\vdash_{\mathrm{full}}^k t:qΓ++[(x,p)]⊢fullk​t:q for any annotation ppp. The five shared rules keep the same mode in all their premises and conclusion. Nullary symbols, zero costs, and zero annotations are included; argument-index conditions for a nullary symbol are vacuous, its ordered argument context is empty, and its argument-cost sum is zero.

Consistency. For every FFF, substitution σ\sigmaσ, and context Γ\GammaΓ, consistency means the conjunction of the following requirements: the keys of Γ\GammaΓ have no repetitions, and for every variable name xxx and annotation qqq such that (x,q)(x,q)(x,q) is an entry of Γ\GammaΓ, one has x∈Dσx\in D_\sigmax∈Dσ​ and there exists a cost b∈Q≥0b\in\mathbb Q_{\ge0}b∈Q≥0​ with []⊢fullbσˉ(x):q[]\vdash_{\mathrm{full}}^b\bar\sigma(x):q[]⊢fullb​σˉ(x):q. The witness bbb may depend on the entry. This definition alone does not require the substitution to be normalised. The empty context is consistent with every substitution.

Freeing arguments. For every FFF, natural number nnn, term family (ti)i<n(t_i)_{i<n}(ti​)i<n​, annotation family (pi)i<n(p_i)_{i<n}(pi​)i<n​, context Γ\GammaΓ, and cost ℓ∈Q≥0\ell\in\mathbb Q_{\ge0}ℓ∈Q≥0​, the freeing condition means that there exist a term family (vi)i<n(v_i)_{i<n}(vi​)i<n​, a total renaming ρ:N→N\rho:\mathbb N\to\mathbb Nρ:N→N, contexts (Γi)i<n(\Gamma_i)_{i<n}(Γi​)i<n​, and costs (bi)i<n(b_i)_{i<n}(bi​)i<n​ in Q≥0\mathbb Q_{\ge0}Q≥0​ such that: the concatenation of all lists V(vi)V(v_i)V(vi​) in index order has no repetitions; renaming every variable of viv_ivi​ by ρ\rhoρ gives exactly tit_iti​ for every iii; for every iii, the key list of Γi\Gamma_iΓi​ is a permutation of V(vi)V(v_i)V(vi​) and Γi⊢footprintbivi:pi\Gamma_i\vdash_{\mathrm{footprint}}^{b_i}v_i:p_iΓi​⊢footprintbi​​vi​:pi​; ℓ=∑i<nbi\ell=\sum_{i<n}b_iℓ=∑i<n​bi​; and Γ\GammaΓ is the context obtained by first concatenating the Γi\Gamma_iΓi​ in index order, then replacing each key xxx by ρ(x)\rho(x)ρ(x), and finally keeping each resulting key once, in its first-occurrence order, with annotation equal to the sum of all original annotations whose renamed keys equal it. The renaming need not be injective, so it can identify different names and add their annotations. When n=0n=0n=0, this condition holds exactly when Γ=[]\Gamma=[]Γ=[] and ℓ=0\ell=0ℓ=0.

Boundedness of one rule. For every FFF, rule rrr, and charge e∈Q≥0e\in\mathbb Q_{\ge0}e∈Q≥0​, boundedness of rrr at charge eee means that for every declaration ((pi),κ,q)∈Dfr((p_i),\kappa,q)\in\mathcal D_{f_r}((pi​),κ,q)∈Dfr​​ there exist a context Γ\GammaΓ and costs ℓ,k∈Q≥0\ell,k\in\mathbb Q_{\ge0}ℓ,k∈Q≥0​ such that the family of left-hand arguments (sr,i)(s_{r,i})(sr,i​) with input annotations (pi)(p_i)(pi​) satisfies the freeing condition with context Γ\GammaΓ and cost ℓ\ellℓ, the exact equality κ+ℓ=e+k\kappa+\ell=e+kκ+ℓ=e+k holds, and Γ⊢fullkur:q\Gamma\vdash_{\mathrm{full}}^k u_r:qΓ⊢fullk​ur​:q. The witnesses may depend on the declaration, and the condition quantifies over all declarations for the head, not merely one selected declaration.

Resource boundedness. For every FFF and Boolean parameter bbb, resource boundedness means that every rule in RRR is bounded at charge 111 if bbb is true and at charge 000 if bbb is false, and every rule in WWW is bounded at charge 000. The parameter defaults to true when omitted. A rule appearing in both lists must satisfy both applicable conditions; a condition on an empty list is vacuous.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me