Added to Favorites

Computing Dictionary

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 (F bottom), ....

The least fixed point is guaranteed to exist for a continuous function over a cpo.

(2005-04-12)

Explore Dictionary.com

More from Thesaurus.com

Synonyms and Antonyms for least fixed point

More from Reference.com

Search for articles containing least fixed point

More from Dictionary.com Translator

Translate least fixed point into French

Translate least fixed point into German

Translate least fixed point into Italian

Translate least fixed point into another language

Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Nearby Words

Copyright © 2014 Dictionary.com, LLC. All rights reserved.