Terms, substitutions, and relative innermost rewriting
DefinitionMoserSchneckenreither_SyntaxA finite signature separates constructors from defined symbols and contains at least one constant. Arity-correct terms use natural-number variables. Rules have a defined root and no extra right-hand-side variables; their patterns may be nonlinear and may contain defined symbols. The relative problem consists of finite strict and weak rule sets. Ordinary rewriting, normal forms, normalised finite substitutions, restricted innermost steps, relative steps, and finite derivations with only strict steps charged are defined directly from rules. A basic term has a defined root and constructor-term arguments, which may contain variables. Constructor-like symbols are precisely constructors and symbols appearing inside a left-hand-side argument. A supported term is ground and contains only these symbols. The two rule sets may overlap; membership in a chosen part determines the charge of that application.
import Mathlib.Data.Finset.Basic
import Mathlib.Data.List.OfFn
import Mathlib.Logic.Relation
/-!
First-order syntax and relative innermost rewriting, following Moser and Schneckenreither,
*Automated Amortised Resource Analysis for Term Rewrite Systems*, arXiv:1811.09071v1,
Section 3, pp. 6–7. Mathematical authorship belongs to Georg Moser and Manuel Schneckenreither.
-/
namespace MoserSchneckenreither
/-- A finite signature with a nonempty constructor part and at least one constant. -/
structure Signature where
count : ℕ
arity : Fin count → ℕ
constructors : Finset (Fin count)
constructors_nonempty : constructors.Nonempty
has_constant : ∃ f, arity f = 0
abbrev Symbol (sig : Signature) := Fin sig.count
/-- Variables are natural numbers; symbol arities are enforced by the term datatype. -/
inductive Term (sig : Signature) where
| var : ℕ → Term sig
| app (f : Symbol sig) : (Fin (sig.arity f) → Term sig) → Term sig
namespace Term
variable {sig : Signature}
def vars : Term sig → List ℕ
| .var x => [x]
| .app _ ts => (List.ofFn fun i ↦ vars (ts i)).flatten
def size : Term sig → ℕ
| .var _ => 1
| .app _ ts => 1 + (List.ofFn fun i ↦ size (ts i)).sum
def subst (σ : ℕ → Term sig) : Term sig → Term sig
| .var x => σ x
| .app f ts => .app f fun i ↦ subst σ (ts i)
def rename (ρ : ℕ → ℕ) (t : Term sig) := t.subst fun x ↦ .var (ρ x)
def Ground (t : Term sig) : Prop := t.vars = []
def Linear (t : Term sig) : Prop := t.vars.Nodup
/-- Constructor terms, including variables, as used in the definition of a basic term. -/
inductive Constructor : Term sig → Prop
| var (x : ℕ) : Constructor (.var x)
| app (f : Symbol sig) (ts : Fin (sig.arity f) → Term sig)
(hf : f ∈ sig.constructors) (ht : ∀ i, Constructor (ts i)) : Constructor (.app f ts)
def Basic : Term sig → Prop
| .var _ => False
| .app f ts => f ∉ sig.constructors ∧ ∀ i, Constructor (ts i)
def symbols : Term sig → List (Symbol sig)
| .var _ => []
| .app f ts => f :: (List.ofFn fun i ↦ symbols (ts i)).flatten
end Term
/-- A rule has a defined root and may have arbitrary, nonlinear argument patterns. -/
structure Rule (sig : Signature) where
head : Symbol sig
args : Fin (sig.arity head) → Term sig
rhs : Term sig
defined_head : head ∉ sig.constructors
no_extra_variables : ∀ x ∈ rhs.vars, x ∈ (Term.app head args).vars
def Rule.lhs {sig : Signature} (r : Rule sig) : Term sig := .app r.head r.args
/-- Lists present finite rule sets; order and duplicate membership do not affect rewriting. -/
structure Problem (sig : Signature) where
strict : List (Rule sig)
weak : List (Rule sig)
def Problem.rules {sig : Signature} (P : Problem sig) := P.strict ++ P.weak
/-- A finite simultaneous substitution, with identity outside its explicit domain. -/
structure Substitution (sig : Signature) where
domain : Finset ℕ
assignment : ℕ → Term sig
def Substitution.apply {sig : Signature} (σ : Substitution sig) (x : ℕ) : Term sig :=
if x ∈ σ.domain then σ.assignment x else .var x
/-- Ordinary rewriting under arbitrary term contexts. -/
inductive Rewrites {sig : Signature} (rules : List (Rule sig)) : Term sig → Term sig → Prop
| root (r : Rule sig) (hr : r ∈ rules) (σ : ℕ → Term sig) :
Rewrites rules (r.lhs.subst σ) (r.rhs.subst σ)
| arg (f : Symbol sig) (ts us : Fin (sig.arity f) → Term sig) (i : Fin (sig.arity f))
(hstep : Rewrites rules (ts i) (us i)) (hrest : ∀ j, j ≠ i → ts j = us j) :
Rewrites rules (.app f ts) (.app f us)
def Normal {sig : Signature} (rules : List (Rule sig)) (t : Term sig) : Prop :=
¬ ∃ u, Rewrites rules t u
def Substitution.Normalised {sig : Signature} (P : Problem sig) (σ : Substitution sig) : Prop :=
∀ x ∈ σ.domain, (σ.assignment x).Ground ∧ Normal P.rules (σ.assignment x)
/-- Restricted steps use rules in `rules` and normalise redex arguments with respect to `Q`. -/
inductive RestrictedStep {sig : Signature} (Q rules : List (Rule sig)) :
Term sig → Term sig → Prop
| root (r : Rule sig) (hr : r ∈ rules) (σ : ℕ → Term sig)
(hnormal : ∀ i, Normal Q ((r.args i).subst σ)) :
RestrictedStep Q rules (r.lhs.subst σ) (r.rhs.subst σ)
| arg (f : Symbol sig) (ts us : Fin (sig.arity f) → Term sig) (i : Fin (sig.arity f))
(hstep : RestrictedStep Q rules (ts i) (us i))
(hrest : ∀ j, j ≠ i → ts j = us j) :
RestrictedStep Q rules (.app f ts) (.app f us)
/-- One relative step is any finite weak prefix, one strict step, and any finite weak suffix. -/
def RelativeStep {sig : Signature} (P : Problem sig) (s t : Term sig) : Prop :=
∃ u v, Relation.ReflTransGen (RestrictedStep P.rules P.weak) s u ∧
RestrictedStep P.rules P.strict u v ∧
Relation.ReflTransGen (RestrictedStep P.rules P.weak) v t
/-- Counted elementary steps retain both the strict and weak parts, including possible overlap. -/
inductive CountedStep {sig : Signature} (P : Problem sig) : ℕ → Term sig → Term sig → Prop
| strict {s t} (h : RestrictedStep P.rules P.strict s t) : CountedStep P 1 s t
| weak {s t} (h : RestrictedStep P.rules P.weak s t) : CountedStep P 0 s t
/-- Finite derivations, charging only strict-rule applications. -/
inductive Derivation {sig : Signature} (P : Problem sig) : Term sig → ℕ → Term sig → Prop
| refl (t) : Derivation P t 0 t
| step {s t u n K} (hstep : CountedStep P K s t) (hrest : Derivation P t n u) :
Derivation P s (K + n) u
/-- Defined symbols below a rule's root must be treated as constructor-like symbols. -/
def ConstructorLike {sig : Signature} (P : Problem sig) (f : Symbol sig) : Prop :=
f ∈ sig.constructors ∨ ∃ r ∈ P.rules, ∃ i, f ∈ (r.args i).symbols
/-- Ground terms containing only constructors and constructor-like symbols. -/
def Supported {sig : Signature} (P : Problem sig) (t : Term sig) : Prop :=
t.Ground ∧ ∀ f ∈ t.symbols, ConstructorLike P f
end MoserSchneckenreither
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
readback_model: GPT-6 (Codex)
Signature. A signature is data consisting of a natural number , an arity function , a finite set , a proof that is nonempty, and a proof that there exists an index with . The indices are the available symbols and is the designated set of constructors. These requirements exclude . The symbol of arity zero need not belong to , and membership in imposes no restriction on arity.
Symbol. For any signature , consisting of a natural number , arities for indices , a nonempty set of those indices, and the existence of at least one index of arity zero, a symbol of is an index with . This is the same type of indices used by the signature, including indices inside and outside ; the signature requirements imply that the type of symbols is nonempty.
Term. For every signature with symbols , an arity for each symbol, a nonempty designated constructor set , and at least one symbol of arity zero, the terms over form the inductively generated type with two constructions: a variable for any , and an application for any symbol and any family of terms indexed by . Thus terms are finite ordered trees, variable labels can be any natural numbers, and every application has exactly its head symbol's prescribed number of children. A symbol of arity zero gives an application with no children. Both constructor symbols and symbols outside can head applications, and the construction does not require a term to contain a variable.
Term.vars. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, and every finite term built from natural-number variables and applications , the variable list is defined recursively as follows: the list for the variable is the one-element list , and the list for an application is the concatenation of the variable lists of in increasing child-index order. Every occurrence is retained, including repeated occurrences of the same variable. An application of arity zero has the empty variable list.
Term.size. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, the size of a finite term built from natural-number variables and symbol applications is a natural number defined recursively by for every variable and . Each variable occurrence and each application contributes one. For an application of arity zero the sum is empty and equals zero, so its size is one.
Term.subst. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, and every total function into the finite terms over these symbols and natural-number variables, substitution sends the variable to and sends to , where the bracket notation denotes this recursively defined operation. The chosen term is returned as it is, so variables inside it are not recursively substituted during that replacement. The function is arbitrary and need not have finite support or ground values; nullary applications are unchanged.
Term.rename. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, every function , and every finite term built from natural-number variables and symbol applications, renaming by means replacing every variable occurrence by the variable and recursively retaining each application head and the ordering of all its children. Equivalently, it is simultaneous substitution with the variable term as the image of . No injectivity or surjectivity is required of , so distinct variable labels may become equal; an application of arity zero is unchanged.
Term.Ground. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, and every finite term built from natural-number variables and symbol applications, is ground exactly when its variable-occurrence list is empty. That list is at a variable and is the ordered concatenation of the children's lists at an application. Consequently this predicate requires the absence of all variable occurrences; every nullary application is ground, regardless of whether its head belongs to the constructor set, whereas a variable term is not ground.
Term.Linear. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, and every finite term built from natural-number variables and symbol applications, is linear exactly when its variable-occurrence list has no duplicate entries. The list contains once for a variable term and is formed at each application by concatenating its children's lists in increasing index order, retaining all occurrences. Thus no natural-number variable label may occur twice anywhere in . A variable term is linear, and every term with no variable occurrences, including every nullary application, is linear because its variable list is empty.
Term.Constructor. For every signature with finitely many symbols , arities , a nonempty designated constructor set , and at least one symbol of arity zero, the constructor-term predicate on finite terms is inductively generated by these clauses: for each , the variable satisfies the predicate; and for every symbol and family of terms , the application satisfies it whenever and every satisfies it. Equivalently, every application symbol in the tree must belong to , while variables are allowed without restriction or a requirement of distinctness. For the child condition is vacuous, so a nullary application satisfies the predicate exactly when its head is in . The signature's required nullary symbol is not required to be in .
Term.Basic. For every signature with finitely many symbols , arities , a nonempty designated constructor set , and at least one symbol of arity zero, a variable term is not basic, and an application is basic exactly when and each child is a finite tree in which every application symbol belongs to , with arbitrary natural-number variables permitted as leaves. In particular, the children need not be ground or have distinct variable occurrences. When the child requirement is vacuous, and basicness is exactly . If every symbol belongs to , there are no basic terms.
Term.symbols. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, the symbol list of a finite term over these symbols and natural-number variables is defined recursively by assigning the empty list to every variable and assigning to the list beginning with followed by the concatenated symbol lists of in increasing child-index order. This records every application-head occurrence, with repetitions retained. In particular, the list for a nullary application is .
Rule. For every signature consisting of finitely many symbols , arities , a nonempty designated constructor set , and at least one symbol of arity zero, a rule consists of a head symbol , a family of argument terms , a right-hand term , a proof that , and a proof that every natural number occurring as a variable in occurs as a variable in the application . Terms here are finite trees of natural-number variables and applications of symbols with their prescribed arities; the variable list is obtained by listing variable leaves in child order, retaining repetitions, and the last requirement is membership inclusion of these lists, with no bound on the multiplicity of a permitted variable in . The arguments may contain arbitrary symbols and repeated variables. If , the left-hand variable list is empty and hence has no variables. A rule can exist only if some symbol lies outside .
Rule.lhs. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set , and at least one symbol of arity zero, and every rule consisting of a head , argument terms , and a right-hand term whose variable labels all occur in those arguments, the left-hand term is defined to be exactly the application . The terms are finite trees of natural-number variables and arity-respecting symbol applications. The right-hand term and the proofs attached to the rule contribute no children to this application. For a nullary head this is the nullary application , and the rule condition then requires to have no variables.
Problem. For every signature with finitely many symbols , arities , a nonempty designated constructor set , and at least one symbol of arity zero, a problem consists of two lists of rules, called its strict list and its weak list. Each rule has the form , where , all terms are finite trees of natural-number variables and arity-respecting symbol applications, and every variable occurring in occurs in some . The two lists may each be empty, may contain repeated rules, and may share rules; there is no further field imposing a relation between the lists or a condition on their combined behavior.
Problem.rules. For every signature with finitely many symbols , arities , a nonempty designated constructor set , and at least one symbol of arity zero, and every problem whose strict and weak components are lists of rules, its combined rule list is its strict list followed by its weak list. A rule here is an application with and with every variable in occurring in the arguments, where all terms are finite arity-respecting symbol trees with natural-number variable leaves. Concatenation preserves the order within each list and every repetition, including a rule appearing in both lists; either list, or both, may be empty.
Substitution. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, a substitution record consists of a finite set called its domain and a total assignment function , where is the type of finite trees of natural-number variables and arity-respecting applications of the symbols. The domain may be empty. The record includes an assigned term for every natural number, including numbers outside , and imposes no condition on these values: neither groundness nor a relationship between and the places where differs from the variable is required.
Substitution.apply. For every signature with finitely many symbols , natural-number arities , a nonempty designated constructor set, and at least one symbol of arity zero, every substitution record with finite and arbitrary total assignment into the finite terms over these symbols and natural-number variables, and every , its applied value at is if , and is the variable term if . Values of outside therefore do not affect this function. The domain may include an for which is already the variable , and for this function returns the variable for every .
Rewrites. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, and every list of rules having and no variable in absent from the arguments, the one-step rewriting relation on finite terms is the least relation with the following two properties. For every rule in and every total assignment of finite terms to variables, it relates to , where substitution simultaneously replaces original variable leaves by their assigned terms, retaining all application heads and their child order. Also, for every symbol , two families of terms and , and an index , it relates to if rewrites to and for every . Thus one rule replacement may occur at any finite position inside a term, with all surrounding symbols and other children retained. The assignment is not required to be ground, finitely supported, or normal. There is no child-position case for a nullary application; with empty no step exists. The source and target are not required to be different, and each relation instance represents one rule replacement rather than a sequence of several replacements.
Normal. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, every rule list , and every finite term , normality of means that there is no finite term obtainable from by one rule replacement anywhere in its tree. Each rule in is with and every variable of occurring in the arguments; a replacement may use any total assignment of finite terms to natural-number variables, simultaneously substitute into both sides, and replace the resulting left side by the resulting right side at the root or inside any child, leaving the surrounding tree and all other children unchanged. Terms are built from natural-number variables and applications of the prescribed arities. The excluded target includes , so a self-replacement prevents normality. No groundness is required; if is empty, every term is normal.
Substitution.Normalised. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, every problem comprising strict and weak rule lists, and every substitution record with finite and total assignment of finite terms , the record is normalised exactly when, for every , the term has no variable occurrences and admits no one-step rewrite using the concatenation of the strict and weak lists. Terms are finite trees of natural-number variables and arity-respecting symbol applications; each rule is with and every variable of present in the arguments. A one-step rewrite replaces at any position an instance of a rule's left side by the corresponding right-side instance under an arbitrary total simultaneous substitution, preserving the surrounding tree and other children; a rewrite back to the same term also violates the required absence of steps. There is no condition on for . For the predicate holds vacuously; if both rule lists are empty, its requirements on the assigned terms reduce to absence of variables.
RestrictedStep. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, and any two lists of rules and , a restricted step is the least relation on finite terms generated as follows. A rule is with and every variable of occurring in the arguments; for each rule in and each total assignment of finite terms to variables, the relation goes from to provided that, for every , there is no ordinary one-step rewrite from using . Substitution replaces variable leaves simultaneously and leaves symbol heads and child order intact; an ordinary rewrite can replace any substituted -rule instance anywhere inside the tested argument, without any further normality condition. For every symbol , term families and , and , a restricted step from to also gives a restricted step between the corresponding -applications when for all . Accordingly the root condition is checked on the immediate arguments of the rule occurrence being replaced, even when that occurrence lies inside a larger term; the contextual clause adds no normality requirement on its other children. Terms may contain natural-number variables, substitutions are arbitrary total assignments, and the two rule lists are independent. The root condition is vacuous for a nullary rule, is automatic for all arguments when is empty, and cannot yield a step when is empty. A source and target may coincide.
RelativeStep. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, every problem with strict list and weak list , and all finite terms , a relative step from to means that there exist finite terms such that reaches by a finite sequence of zero or more restricted -steps, makes one restricted -step to , and reaches by a finite sequence of zero or more restricted -steps. Every restricted step uses followed by as its normality-test list: at a chosen position, a rule from the step's designated list is simultaneously instantiated by an arbitrary total assignment of finite terms to natural-number variables, each instantiated argument must admit no ordinary one-step replacement anywhere within it by any instantiated rule from either list, and the instantiated left side is replaced by the instantiated right side, retaining the surrounding tree and all other children. All terms are finite arity-respecting symbol trees with natural-number variables; each rule has and no right-side variable absent from its arguments. For nullary rules the argument condition is vacuous. Either weak sequence may have length zero, allowing or , but a strict step is required. In particular no relative step exists if is empty, and if is empty this relation is exactly the stated single restricted strict step. The lists may overlap or contain repetitions, and the endpoints may coincide if the required steps exist.
CountedStep. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, every problem with strict list and weak list , every natural number , and all finite terms , a counted step of count from to is generated by precisely two alternatives: a restricted step using a rule in gives count , and a restricted step using a rule in gives count . In each alternative the normality-test list is the concatenation of and : at any chosen position one simultaneously instantiates a rule by an arbitrary total assignment of finite terms to natural-number variables, requires every instantiated immediate argument to have no ordinary one-step rewrite at any position by any instantiated rule from either list, and replaces the instantiated left side by the right side while retaining its context. Rules have and no right-side variable absent from their arguments; terms are finite arity-respecting symbol trees with natural-number variable leaves. For a nullary rule the argument requirement is vacuous. No counted step has , and an empty designated list provides no step of its corresponding kind. The two alternatives need not be disjoint: the same pair of terms can have both counts when both restricted relations hold, including when a usable rule belongs to both lists.
Derivation. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, and every problem with strict list and weak list , the derivation relation associates an initial finite term, a natural-number count, and a final finite term by the following inductive clauses: every term has a derivation from to itself of count zero; and, for all finite terms and all , a counted step of count from to together with a derivation of count from to gives a derivation of count from to . A counted step is one restricted strict-rule step with count one or one restricted weak-rule step with count zero. Such a step uses an arbitrary total substitution of finite terms for natural-number variables in a rule , replaces the instantiated left side by the right side at any position while retaining its context, and requires every instantiated argument to admit no ordinary one-step rewrite using any rule in either list; this argument requirement is vacuous for a nullary rule. Rules have and every right-side variable occurs in their arguments, and terms are finite arity-respecting symbol trees with natural-number variables. Thus a derivation is a finite sequence of these steps whose count is the sum of its chosen zero-or-one step counts. A zero-count derivation need not be empty: its steps, if present, are weak steps, with no separate bound imposed on their finite number, and its endpoints may differ. The empty sequence always has equal endpoints and count zero. If both lists are empty, only the empty derivations exist. If both step classifications apply to the same pair, either classification can be used in a derivation.
ConstructorLike. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, every problem comprising strict and weak lists of rules, and every symbol , being constructor-like means that either , or there exist a rule in the strict list followed by the weak list and an index such that occurs as an application symbol somewhere in the argument term . Terms are finite trees of natural-number variables and arity-respecting symbol applications, each rule has and every variable of occurs in its arguments, and a term's symbol occurrences include its application head and recursively all its children's application heads, with variables contributing none. The occurrence may therefore be at the root of or at any deeper position. The second alternative tests the actual argument terms of the rule, without substitution, and does not require that the rule can be used in a derivation. A nullary rule supplies no argument index and hence no witness for this alternative. If both lists are empty, the predicate reduces to ; symbols outside can satisfy it through occurrences in rule arguments.
Supported. For every signature with finitely many symbols , arities , a nonempty constructor set , and at least one symbol of arity zero, every problem with strict and weak rule lists, and every finite term , being supported means both that has no occurrences of natural-number variables and that every symbol occurring as an application head anywhere in either belongs to or occurs as an application head somewhere in an argument of some rule in the concatenation of the strict and weak lists. Each such rule is with and every variable of present in the arguments; all terms are finite trees of applications with their prescribed arities and natural-number variable leaves. More explicitly, for each symbol occurring in , the second alternative requires a rule in that concatenated list and an index for which occurs at the root of or deeper in its tree; the rule and index may depend on , and its argument is examined without substitution. Variable terms fail the first conjunct. A nullary application satisfies the first conjunct automatically and is supported exactly when its head satisfies the stated symbol condition. A nullary rule cannot supply a witness through one of its arguments. If both rule lists are empty, supported terms are exactly variable-free terms all of whose application symbols belong to ; the signature's existence of some nullary symbol does not require that symbol to belong to .