Least fixed point

In order theory, a branch of mathematics, the least fixed point (lfp or LFP, sometimes also smallest fixed point) of a function from a partially ordered set to itself is the fixed point which is less than each other fixed point, according to the set's order. A function need not have a least fixed point, and cannot have more than one.

The function f(x)=x²-4 has two fixed points, shown as the intersection with the blue line; its least one is at 1/2-√17/2.

For example, with the usual order on the real numbers, the least fixed point of the real function f(x) = x² is x = 0 (since the only other fixed point is 1 and 0 < 1). In contrast, f(x) = x+1 has no fixed point at all, let alone a least one, and f(x)=x has infinitely many fixed points, but no least one.

Applications

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 related to making recursive definitions (see domain theory and/or denotational semantics for details).

Immerman [1][2] and Vardi [3] independently showed the descriptive complexity result that the polynomial-time computable properties of linearly ordered structures are definable in FO(LFP), i.e. in first-order logic with a least fixed point operator. However, FO(LFP) is too weak to express all polynomial-time properties of unordered structures (for instance that a structure has even size).

Examples

Let G=(V,A) be a directed graph and v be a vertex. The set of nodes accessible from v can be defined as the set S which is the least fixed-point for the property: v belongs to S and if w belongs to S and there is an edge from w to x, then x belongs to S. The set of nodes which are co-accessible from v is defined by a similar least fix-point. On the one hand the strongly connected component of v is the intersection of those two least fixed-point.

Let G be a proper context-free grammar. The set E of symbols which produces the emptyword is defined as the least fixed-point which contains the symbols S such that $S\rightarrow \varepsilon$ , or such that $S\rightarrow S^{0},\dots ,S^{n}$ where all symbols $S^{i}$ belongs to E.

Greatest fixed points

Greatest fixed points can also be determined, but they are less commonly used than least fixed points. However, in computer science they, analogously to the least fixed point, give rise to corecursion and codata.

gollark: ```lua local function do_things(x) for i = 1, x doprint "hello" end end```

gollark: It will write code, but do inverse indenting, like this:

gollark: Actually, in the UK I think that's fairly normal.

gollark: It will devour all light in this universe and the next.

gollark: It will tear apart the very fabric of space and time so that it may torture you more thoroughly.

Notes

N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.
Immerman, Neil (1982). "Relational Queries Computable in Polynomial Time". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 147–152. doi:10.1145/800070.802187. Revised version in Information and Control, 68 (1986), 86–104.
Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 137–146. doi:10.1145/800070.802186.

References

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.

[2] Immerman, Neil (1982). "Relational Queries Computable in Polynomial Time". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 147–152. doi:10.1145/800070.802187. Revised version in Information and Control, 68 (1986), 86–104.

[3] Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 137–146. doi:10.1145/800070.802186.