CATEGORIES:
BiologyChemistryConstructionCultureEcologyEconomyElectronicsFinanceGeographyHistoryInformaticsLawMathematicsMechanicsMedicineOtherPedagogyPhilosophyPhysicsPolicyPsychologySociologySportTourism
Lexicographic order
The words in a dictionary are listed in alphabetic, or lexicographic, order, which is based on the ordering of the letters in the alphabet. This is a special case of an ordering of strings on a set constructed from a partial ordering on the set.
The lexicographic ordering 
on 
is defined by specifying that one pair is less than a second pair if the first entry of the first pair isles than (in A1) the first entry of the second pair, or if the first entries are equal, but the second entry of this pair is less than (in A2) the second entry of the second pair. In other words, 
, either if 
or if both 
and 
. We obtain a partial ordering by adding equality to the ordering 
on .
Example. Determine whether 
, whether 
, whether 
in the poset 
, where is the lexicographic ordering constructed from the usual ≤ relation on Z.
A lexicographic ordering can be defined on the Cartesian product of n posets 
, 
, …, 
. Define the partial ordering on 
by 
if , or if there is an integer 
such that 
and 
.
We can now define lexicographic ordering of strings. Consider the strings 
and 
on a partially ordered set S. Suppose these strings are not equal. Let t be the minimum of m and n. The definition of lexicographic ordering is that the string is less than iff 
or 
and m < n where in this inequality represents the lexicographic ordering of S t.
Example. Consider the set of strings of lowercase English letters. Using the ordering of letters in the alphabet, a lexicographic ordering on the set of strings can be constructed. A string is less than a second string if the letter in the first string in the first position where the strings differ comes before the letter in the second string in this position, or if the first string and the second string agree in all positions, but the second string has more letters. This ordering is the same as that used in dictionaries. For example, discreet discrete, since these strings differ first in the seventh position, and e t. Also, discreet discreetness, since the first eight letters agree, but the second string is longer. Furthermore, discrete discretion, since discrete discreti.
Date: 2015-01-02; view: 1325
| <== previous page | | | next page ==> |
| Partial orderings | | | Hasse diagrams |