Term measures and canonical list inputs
DefinitionAehligSchwichtenberg2002V2_BoundsThe syntactic length and the function used to count reduction steps. In a list iteration over entries the multiplier is the truncated identity . Canonical binary-list inputs are normal and typed, with pairwise disjoint token contexts for a tuple of inputs.
import Definitions.Def_AehligSchwichtenberg2002V2_Syntax
/-!
# Term Length and Polynomial Step Bounds for Aehlig–Schwichtenberg (2002, Section 4)
Source: Klaus Aehlig and Helmut Schwichtenberg,
"A syntactical analysis of non-size-increasing polynomial time computation",
*ACM Transactions on Computational Logic* 3(3), 2002, pp. 383–401 (arXiv:cs/0011037v2),
Section 4 (pp. 9–14).
This module formalizes:
- Definition 4.1: Term length `|t|` (`termLength`, p. 10), with `|{t}| = 0`.
- Definition 4.5: Polynomial bound `ϑ(t) ∈ N^{poly}` (`theta t : Nat → Nat`, p. 11),
pointwise order `PolyLe` (`f ≼ g`), and polynomial boundedness (`IsPolyBounded`).
- Input list representations for Corollary 4.4 (Non-size-increasing property, p. 11) and
Corollary 4.9 (Polynomial-time computability of closed terms of type `L(B) ⊸ ⋯ ⊸ L(B) ⊸ L(B)`, p. 14).
-/
namespace AehligSchwichtenberg2002V2
/-- Definition 4.1 (Length `|t|`, p. 10):
- `|c| := |x| := 1`
- `|t s| := |t| + |s|`
- `|λx^τ. s| := |s| + 1`
- `|⟨t, s⟩| := max {|t|, |s|} + 1`
- `|{t}| := 0`. -/
def termLength : Term → Nat
| .var _ => 1
| .const _ => 1
| .app t s => termLength t + termLength s
| .lam _ s => termLength s + 1
| .pair t s => Nat.max (termLength t) (termLength s) + 1
| .brace _ => 0
/-- Section 4 (p. 11): `X_n(m) = min {n, m}`. -/
def truncId (n m : Nat) : Nat :=
Nat.min n m
/-- Pointwise order `f ≼ g` on functions `Nat → Nat` (Section 4, p. 11). -/
def PolyLe (f g : Nat → Nat) : Prop :=
∀ m : Nat, f m ≤ g m
/-- Definition 4.5 (Polynomial bound `ϑ(t)` of a term, p. 11):
For each (not necessarily typed) term `t` and input parameter `m : Nat`, `theta t m`
evaluates the polynomial bound `ϑ(t)(m)`:
- `ϑ(x) := ϑ(c) := 0`
- `ϑ(t s) := ϑ(t) + X_n · ϑ(h) + X_n · |h|` if `t` is a list with `n` entries and `s = {h}`,
and `ϑ(t) + ϑ(s)` otherwise
- `ϑ(λx^τ. t) := ϑ(t)`
- `ϑ(⟨t, s⟩) := sup_{≼} {ϑ(t), ϑ(s)}`
- `ϑ({h}) := X · ϑ(h) + X · |h|`. -/
def theta : Term → Nat → Nat
| .var _, _ => 0
| .const _, _ => 0
| .app t (.brace h), m =>
match listEntryCount t with
| some n =>
theta t m + truncId n m * theta h m + truncId n m * termLength h
| none =>
theta t m + (m * theta h m + m * termLength h)
| .app t s, m => theta t m + theta s m
| .lam _ t, m => theta t m
| .pair t s, m => Nat.max (theta t m) (theta s m)
| .brace h, m => m * theta h m + m * termLength h
/-- Combined measure `ϑ(t)(N) + |t|` appearing in Theorem 4.8 (p. 12). -/
def stepMeasure (t : Term) (N : Nat) : Nat :=
theta t N + termLength t
/-- Brace-nesting depth of a term `t` (Section 2, p. 4: "the degree of the bounding polynomial
is the nesting depth of braces"). -/
def braceDepth : Term → Nat
| .var _ => 0
| .const _ => 0
| .lam _ t => braceDepth t
| .pair t s => Nat.max (braceDepth t) (braceDepth s)
| .app t s => Nat.max (braceDepth t) (braceDepth s)
| .brace h => braceDepth h + 1
/-- A function `B : Nat → Nat` is bounded by a polynomial of degree at most `d`
if there exist `c₀, c₁ : Nat` such that `B n ≤ c₀ * (n + 1)^d + c₁` for all `n`. -/
def IsPolyBoundedOfDegree (B : Nat → Nat) (d : Nat) : Prop :=
∃ c₀ c₁ : Nat, ∀ n : Nat, B n ≤ c₀ * (n + 1) ^ d + c₁
/-- A function `B : Nat → Nat` is polynomially bounded (`B ∈ N^{poly}`, p. 11). -/
def IsPolyBounded (B : Nat → Nat) : Prop :=
∃ d : Nat, IsPolyBoundedOfDegree B d
/-- An almost closed normal list of type `L(τ)` with `n` entries (used as canonical list input
in Corollary 4.4, p. 11 & Corollary 4.9, p. 14). -/
def IsCanonicalListInput (τ : Ty) (l : Term) (n : Nat) : Prop :=
∃ Γ : Context,
(∀ v ∈ Γ, v.ty = .diamond) ∧
HasType Γ l (.list τ) ∧
IsNormal l ∧
listEntryCount l = some n
/-- A tuple of canonical binary-list inputs `ls = [l₁, ..., lₖ]` of type `L(B)` with pairwise
disjoint contexts `Γ₁, ..., Γₖ` (Corollary 4.9, p. 14). -/
inductive ValidBinListInputs : Context → List Term → List Nat → Prop where
| nil : ValidBinListInputs [] [] []
| cons {Γ_acc Γ_l Γ_new : Context} {l : Term} {n : Nat} {ls : List Term} {ns : List Nat} :
(∀ v ∈ Γ_l, v.ty = .diamond) →
HasType Γ_l l Ty.bin →
IsNormal l →
listEntryCount l = some n →
IsDisjointCtxUnion Γ_acc Γ_l Γ_new →
ValidBinListInputs Γ_acc ls ns →
ValidBinListInputs Γ_new (l :: ls) (n :: ns)
/-- Sum of list lengths `n₁ + ⋯ + nₖ` for a tuple of list inputs. -/
def sumListLengths : List Nat → Nat
| [] => 0
| n :: ns => n + sumListLengths ns
end AehligSchwichtenberg2002V2
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
The term length gives a variable or constant , an application the sum of its two lengths, an abstraction its body length plus , a pair the maximum of its two lengths plus , and a brace .
For all natural numbers , the truncated identity takes the value , including if either argument is .
For functions , the relation holds if for every natural number .
For each , the weight is on variables and constants, uses the body weight on abstractions, uses the maximum of the two weights on pairs, and gives weight . The weight of is the sum of the weights of when the argument is other than a brace. The weight of is , with if returns and when the count is undefined. In particular, all terms have weight at . The optional list entry count returns on any , returns on if returns a number, and is undefined otherwise. It looks at the rightmost tail argument of each fully applied , permits any parameters on the constructors along that chain, and ignores the contents of the other two arguments.
For every term and , the step measure is . At this is .
The brace depth gives variables and constants , takes the body depth for an abstraction, the maximum of the two depths for a pair or an application, and the contents' depth plus for a brace.
For a function and a degree parameter , the polynomial bound of degree parameter means there are constants such that for every . The constants can be zero, and allows a constant upper bound.
A function is polynomially bounded if there exists for which there are such that for every .
For a type , a term and , a canonical list input of type and count means there is a context consisting entirely of variables of type with , normal, and returning . The context can be empty. The case is a nil constant of the given list type. The types are generated by , , arrows , tensors , products , and lists . A variable is a pair of a natural-number identifier and a type. Equality of variables compares both entries. The terms are variables, constants, abstractions , pairs , applications , and braces . Successive applications associate to the left and arrow chains associate to the right. The constants and have declared type . For every type , the constants and have declared types and . For all types , has declared type . Contexts are lists of variables. A context is a union of two operand contexts if each variable belongs to the result exactly when it belongs to at least one operand. A disjoint union additionally requires that the operands have no common variable. These relations permit arbitrary ordering and repetitions within a context. The typing relation is generated by the variable rule in any context containing that variable, and the constant rule in any context with the declared constant type. An abstraction has type in if has declared type and has type in a union of and the singleton list . An application has type in a disjoint union of contexts typing at and at . The pair has type if has type and has type in the same context. A term of product type gives applications and of types and in its context. If has Boolean type and both and have type in a shared context disjoint from the context of , then has type in their disjoint union. For distinct variables of types , respectively, has type in a disjoint union of a context typing at and a context disjoint from , provided has type in a union of and . If has type and has type in the empty context, has type in the context of . A term is normal when none of the nodes reached from its root through only application nodes, including the root itself, has any of these forms. The forms are an applied abstraction, a pair applied to or , or applied to a pair, applied to two terms and a double abstraction whose distinct binders have types , applied to a brace and another term, and a fully applied with a countable tail further applied to a brace and another term. Abstractions, pairs and braces are normal at the root regardless of their contents.
For a context , a list of terms and a list of natural numbers , validity of binary list inputs is generated from the triple of three empty lists. A rule prepends a term to the tail term list and a number to the tail number list when the tail lists have a valid context and there is a context consisting entirely of variables of type with , normal, and returning . The new context must be a disjoint union of and . The term and number lists therefore have the same length and their entries are matched in order. In the empty case the context must be the empty list.
The sum of a list of natural numbers is for the empty list, and is plus the sum of the tail for a list with first entry .