least fixed point

(redirected from Least fixpoint)

least fixed point

(mathematics)
A function f may have many fixed points (x such that f x = x). For example, any value is a fixed point of the identity function, (\ x . x).

If f is recursive, we can represent it as

f = fix F

where F is some higher-order function and

fix F = F (fix F).

The standard denotational semantics of f is then given by the least fixed point of F. This is the least upper bound of the infinite sequence (the ascending Kleene chain) obtained by repeatedly applying F to the totally undefined value, bottom. I.e.

fix F = LUB bottom, F bottom, F.

The least fixed point is guaranteed to exist for a continuous function over a cpo.
Mentioned in ?
References in periodicals archive ?
A fixpoint d [element of] D is called the least fixpoint if d ?
h] found as above is the least fixpoint, since the bottom [perpendicular to] is the least element and that all functions in F are monotone.
Program [right arrow] C be a semantic evaluation function, associating with each P [element of] Program its least fixpoint semantics [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where every [T.
A least fixpoint abstract interpretation <[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]> is fixpoint complete for <[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]> whenever, for all programs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
p] whose least fixpoint characterizes the semantics of a disjunctive logic program P.
The least fixpoint of T, if it exists, is written as lfp(T).
Abstract interpretation provides a way of approximating these fixpoints via a technique known as "widening"--which can compute an upper bound to a least fixpoint in finite time.
is a subset of the least fixpoint of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; similarly, every element in the sequence False [equivalent] 0, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], .
By the language restriction that [Lambda]x [multiplied by] E must be refinement-monotone in f, we ensure that f is [contains or equal to]-monotone, and therefore the generalized limit theorem [Hitchcock and Park 1972; Nelson 1989] ensures that a least fixpoint exists.
While the top-down approach propagates the information in the same direction as SLD-resolution does, the bottom-up approach propagates the information as in the computation of the least fixpoint of the immediate consequences operator [T.
f(C) is defined by the equations in Table II where [Mu] denotes the least fixpoint with respect subset inclusion of elements of ?
Similarly, safety properties correspond to greatest fixpoints while liveness is expressed through least fixpoints.

Site: Follow: Share:
Open / Close