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 (F bottom), ...}.
The least fixed point is guaranteed to exist for a continuous function over a cpo.

Last updated: 2005-04-12

least recently used

(operating systems) (LRU) A rule used in a paging system which selects a page to be paged out if it has been used (read or written) less recently than any other page. The same rule may also be used in a cache to select which cache entry to flush.

This rule is based on temporal locality - the observation that, in general, the page (or cache entry) which has not been accessed for longest is least likely to be accessed in the near future.

Last updated: 1995-02-15

least significant bit

<data>

(LSB) Bit zero, the bit of a binary number giving the number of ones, the last or rightmost bit when the number is written in the usual way.

Last updated: 1995-07-13

least upper bound

<theory>

(lub or "join", "supremum") The least upper bound of two elements a and b is an upper bound c such that a <= c and b <= c and if there is any other upper bound c' then c <= c'. The least upper bound of a set S is the smallest b such that for all s in S, s <= b. The lub of mutually comparable elements is their maximum but in the presence of incomparable elements, if the lub exists, it will be some other element greater than all of them.

Lub is the dual to greatest lower bound.

(In LaTeX, "<=" is written as \sqsubseteq, the lub of two elements a and b is written a \sqcup b, and the lub of set S is written as \bigsqcup S).

Last updated: 1995-02-03

Nearby terms:

leased line ♦ least fixed point ♦ least recently used ♦ least significant bit

Try this search on Wikipedia, Wiktionary, Google, OneLook.

Loading