The Setting
A normalization candidate at a type restricts its typed terms by their behavior under application. The tests are finite argument stacks whose successive arguments are strongly normalizing at the domains they encounter. Profile regions organize these candidates, and a component interpretation assigns them to types after substitution.
Fix a pure type specification with arbitrary axiom and product-rule relations.✦ Its terms form the collection generated by variables, sorts , applications , annotated abstractions , and dependent products .✦ We use named binders in formulas; indexed variables are de Bruijn indices, with zero denoting the nearest binder, and finite contexts are written newest first. The typing judgement is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules for . A valid context is obtained from the empty context by successive extensions with for some .✦
Full one-step reduction contracts to and is closed under every term position, including annotations and binder bodies.✦ Convertibility is its equivalence closure.✦ A normal term has no one-step reduct.✦ A weakly normalizing term reaches a normal term in finitely many steps; its chosen normal form is denoted . The choice has a fixed fallback for terms without a normal form. Write when reduction is well-founded from .✦ A term is legal in when it occurs as subject or expected type in a typing judgement.✦ System weak normalization requires weak normalization of every legal term in every valid context.✦
Substitutions and Tower Typing
A simultaneous substitution is a function assigning a term to each free indexed variable; its action extends through every term constructor and lifts under binders to avoid capture.✦ Write for its action. Variable renaming acts in the same way with variable images.✦ The single-variable substitution for sends zero to and to the variable ; its action gives bound-variable instantiation . Substitution extension sends zero to and to .✦
A saturated context tower is a family of valid contexts of length , each extending its predecessor by a type having a sort there. Tower expressions use fixed levels for free names. For a tower expression , the term is obtained by the renaming that sends a free level to and leaves other free indices unchanged, with the renaming lifted under binders. Writing for the extension of by a newest declaration of type , saturation requires that, whenever , every bound admits an with . Tower typing is the finite-stage judgement in (1). (1)✦
Context variable lookup gives the declared type at index as viewed in the full context: the newest declaration is shifted once, and passing another declaration shifts the lookup type again.✦ A tower-typed substitution is a simultaneous substitution assigning each variable with lookup a term with .✦ An expected type in is a term that is a sort constant or satisfies for some sort .✦
For a term and a finite list , the iterated application is the term specified by , with .✦ An argument list takes one reduction step by reducing one entry.✦ Write when this list reduction is well-founded from .✦ A strongly normalizing argument list is a finite list of terms from which no infinite sequence of argument list reductions starts.
Sort Profiles and Their Predecessors
The normal-form sort profiles and of a term in a context and in the tower are the sets in (2); they retain every sort typing the chosen normal form. (2) A feasible profile is a nonempty set equal to for some valid context and normal term . For sets of sorts , the product output profile is the set of sorts with for some and .✦ A feasible product profile triple consists of feasible profiles with .✦
The primary signed graph has a positive edge for feasible profiles with . Each feasible product profile triple gives a negative domain edge and a positive codomain edge ; these are all its edges. A signed directed walk is a finite sequence of these edges, including the empty walk; its parity is the number of negative edges modulo two.✦ Directed reachability means that such a walk exists from to , with either parity.✦
The Definition
Definition 1. For the tower , an actual type is a term satisfying (3). (3)✦ The set of typed strongly normalizing terms at is defined by (4). (4)✦ The tested stacks are the least family of finite argument lists generated by (5). (5)✦ The ground candidate is the set in (6). (6)✦
A set is closed under head expansion at if it satisfies (7) for every . (7) A normalization candidate at is a set of terms satisfying (8). (8)✦
For regions , is processed relative to when the conditions in (9) hold for all profiles and all terms . (9)✦
Suppose is system weakly normalizing. A component interface on is a family of environment sets , tower-typed substitutions for , an extension relation for and terms , and interpretations satisfying the laws in (10). Every tower-typed substitution from occurs as some . Put and . In the conversion and outside laws, are expected types as applicable; the candidate law also requires expected. In the weakening law, is expected and . Both product laws require and ; specialization additionally requires . For a term , the term is obtained by the renaming that increases every free index of by one. All the laws hold for every choice of the displayed terms and environments. (10)✦
What Is Checked
The definitions are stated over an arbitrary pure type specification and a saturated context tower, with system weak normalization assumed for the component interface. Equality of terms is decidable whenever equality of the sorts is decidable.