Least fixed point
For example, the least fixed point of the real function
- f(x) = x2
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.
Immerman  and Vardi  independently showed the descriptive complexity result that the polynomial-time computable properties of linearly ordered structures are deﬁnable in LFP. However, LFP is too weak to express all polynomial-time properties of unordered structures (for instance that a structure has even size).
Greatest fixed points
Greatest fixed points can also be determined, but they are less commonly used than least fixed points.
- N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.
- M. Y. Vardi, The complexity of relational query languages, in: Proc. 14th ACM Symp. on Theory of Computing, 1982, pp. 137–146.
- Immerman, Neil. Descriptive Complexity, 1999, Springer-Verlag.
- Libkin, Leonid. Elements of Finite Model Theory, 2004, Springer.
|This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.|