Lexicographical Order - Ordering of Sequences of Various Lengths

Ordering of Sequences of Various Lengths

Given a partially ordered set A, the above considerations allow to define naturally a lexicographical partial order over the free monoid A* formed by the set of all finite sequences of elements in A, with sequence concatenation as the monoid operation, as follows:

if
  • is a prefix of, or
  • and, where is the longest common prefix of and, and are members of A such that, and and are members of A*.

If < is a total order on A, then so is the lexicographic order A*. If A is a finite and totally ordered alphabet, A* is the set of all words over A, and we retrieve the notion of dictionary ordering used in lexicography that gave its name to the lexicographic orderings. However, in general this is not a well-order, even though it is on the alphabet A; for instance, if A = {a, b}, the language {anb | n ≥ 0} has no least element: ... aab ab b. A well-order for strings, based on the lexicographical order, is the shortlex order.

Similarly we can also compare a finite and an infinite string, or two infinite strings.

Comparing strings of different lengths can also be modeled as comparing strings of infinite length by right-padding finite strings with a special value that is less than any element of the alphabet.

This ordering is the ordering usually used to order character strings, including in dictionaries and indexes.

Read more about this topic:  Lexicographical Order

Famous quotes containing the words ordering of, ordering and/or lengths:

    “Seeing then that truth consisteth in the right ordering of names in our affirmations, a man that seeketh precise truth had need to remember what every name he uses stands for, and to place it accordingly, or else he will find himself entangled in words, as a bird in lime twigs, the more he struggles, the more belimed.”
    —Thomas Hobbes (1588–1679)

    “Our goal as a parent is to give life to our children’s learning—to instruct, to teach, to help them develop self-discipline—an ordering of the self from the inside, not imposition from the outside. Any technique that does not give life to a child’s learning and leave a child’s dignity intact cannot be called discipline—it is punishment, no matter what language it is clothed in.”
    —Barbara Coloroso (20th century)

    “You’ll see certain Pythagoreans whose belief in communism of property goes to such lengths that they pick up anything lying about unguarded, and make off with it without a qualm of conscience as if it had come to them by law.”
    —Desiderius Erasmus (c. 1466–1536)