Partially Ordered Set - Linear Extension

Linear Extension

A partial order ≤* on a set X is an extension of another partial order ≤ on X provided that for all elements x and y of X, whenever, it is also the case that x ≤* y. A linear extension is an extension that is also a linear (i.e., total) order. Every partial order can be extended to a total order (order-extension principle).

In computer science, algorithms for finding linear extensions of partial orders (represented as the reachability orders of directed acyclic graphs) are called topological sorting.

Read more about this topic:  Partially Ordered Set

Famous quotes containing the word extension:

    We are now a nation of people in daily contact with strangers. Thanks to mass transportation, school administrators and teachers often live many miles from the neighborhood schoolhouse. They are no longer in daily informal contact with parents, ministers, and other institution leaders . . . [and are] no longer a natural extension of parental authority.
    James P. Comer (20th century)