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.