Least fixed point

Least fixed point

In order theory, a branch of mathematics, the least fixed point (lfp or LFP) of a function is the fixed point which is less than or equal to all other fixed points, according to some partial order.

For example, the least fixed point of the real function

:"f"("x") = "x"2

is "x" = 0 with the usual order on the real numbers (since the only other fixpoint is 1 and 0 < 1). Many fixed-point theorems yield algorithms for locating the least fixed point. Least fixed points often have desirable properties that arbitrary fixed points do not.

In mathematical logic and computer science, the least fixed point is somehow related to making recursive definitions (see domain theory and/or denotational semantics for details).

Immerman [N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.] and Vardi [M. Y. Vardi, The complexity of relational query languages, in: Proc. 14th ACM Symp. on Theory of Computing, 1982, pp. 137–146.] independently showed the descriptive complexity result that the polynomial-time computable properties of linearly ordered structures are definable in LFP. However, LFP is too weak to express all polynomial-time properties of unordered structures (for instance that a structure has even size).

Notes

See also

*Greatest fixed point (less commonly used)
*Kleene fixpoint theorem
*Knaster–Tarski theorem

References

* Immerman, Neil. "Descriptive Complexity", 1999, Springer-Verlag.
* Libkin, Leonid. "Elements of Finite Model Theory", 2004, Springer.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Fixed point (mathematics) — Not to be confused with a stationary point where f (x) = 0. A function with three fixed points In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is a point[1] that is …   Wikipedia

  • Fixed point theorem — In mathematics, a fixed point theorem is a result saying that a function F will have at least one fixed point (a point x for which F ( x ) = x ), under some conditions on F that can be stated in general terms. Results of this kind are amongst the …   Wikipedia

  • Greatest fixed point — In mathematics, more specifically in order theory, the greatest fixed point (gfp or GFP) of a function is the fixed point which is greater than or equal to to all other fixed points, according to some partial order. For example, the greatest… …   Wikipedia

  • Fixed-point combinator — Y combinator redirects here. For the technology venture capital firm, see Y Combinator (company). In computer science, a fixed point combinator (or fixpoint combinator[1] ) is a higher order function that computes a fixed point of other functions …   Wikipedia

  • Fixed-point arithmetic — In computing, a fixed point number representation is a real data type for a number that has a fixed number of digits after (and sometimes also before) the radix point ( e.g. , after the decimal point . in English decimal notation). Fixed point… …   Wikipedia

  • fixed-point theorem — ▪ mathematics       any of various theorems in mathematics dealing with a transformation of the points of a set into points of the same set where it can be proved that at least one point remains fixed. For example, if each real number is squared …   Universalium

  • Fixed point combinator — A fixed point combinator (or fixed point operator) is a higher order function that computes a fixed point of other functions. This operation is relevant in programming language theory because it allows the implementation of recursion in the form… …   Wikipedia

  • Fixed point iteration — In numerical analysis, fixed point iteration is a method of computing fixed points of iterated functions.More specifically, given a function f defined on the real numbers with real values and given a point x 0 in the domain of f, the fixed point… …   Wikipedia

  • Brouwer fixed point theorem — In mathematics, the Brouwer fixed point theorem is an important fixed point theorem that applies to finite dimensional spaces and which forms the basis for several general fixed point theorems. It is named after Dutch mathematician L. E. J.… …   Wikipedia

  • Lefschetz fixed-point theorem — In mathematics, the Lefschetz fixed point theorem is a formula that counts the number of fixed points of a continuous mapping from a compact topological space X to itself by means of traces of the induced mappings on the homology groups of X . It …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”