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:
“Slavery is founded in the selfishness of mans natureopposition to it, is [in?] his love of justice.... Repeal the Missouri compromiserepeal all compromisesrepeal the declaration of independencerepeal all past history, you still can not repeal human nature. It still will be the abundance of mans heart, that slavery extension is wrong; and out of the abundance of his heart, his mouth will continue to speak.”
—Abraham Lincoln (18091865)