Recurrences depending on earlier coordinates #
Each coordinate may inspect only its strict prefix. Over a well-founded order of coordinates,
such equations have at most one solution (Function.UsesPrefix.fixedPoint_unique); the
coordinates can be Fin n, or ℕ for a stream. Over Fin n the solution is computed by
well-founded recursion. When the coordinate operations are continuous, this solution is also
their least fixed point. The values may themselves contain partial information or errors.
Compute a finite recurrence using only already computed coordinates.
Equations
- Function.prefixRecursion step i = step i fun (j : Fin ↑i) => Function.prefixRecursion step ⟨↑j, ⋯⟩
Instances For
Coordinate i depends only on coordinates strictly before i.
Equations
- Function.UsesPrefix f = ∀ (i : ι) (x y : ι → α), (∀ j < i, x j = y j) → f x i = f y i
Instances For
A prefix-dependent system over well-founded coordinates has at most one solution, even with partial values.
Assemble continuous operations on strict prefixes into simultaneous equations.
Equations
- OmegaCompletePartialOrder.ContinuousHom.prefixMap step = OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (x : Fin n → D) (i : Fin n) => (step i) fun (j : Fin ↑i) => x ⟨↑j, ⋯⟩) ⋯
Instances For
The assembled equations depend only on earlier coordinates.
Well-founded evaluation satisfies the simultaneous equations.
The least fixed point of finite prefix equations is their computed solution.