Editing Lexicographic order (section)

==Monoid of words==

The {{em|monoid of words}} over an alphabet {{math|''A''}} is the [[free monoid]] over {{math|''A''}}. That is, the elements of the monoid are the finite sequences (words) of elements of {{math|''A''}} (including the empty sequence, of length 0), and the operation (multiplication) is the [[concatenation]] of words. A word {{math|''u''}} is a [[prefix (computer science)|prefix]] (or 'truncation') of another word {{math|''v''}} if there exists a word {{math|''w''}} such that {{math|1=''v'' = ''uw''}}. By this definition, the empty word (<math>\varepsilon</math>) is a prefix of every word, and every word is a prefix of itself (with {{math|''w''}} <math> = \varepsilon</math>); care must be taken if these cases are to be excluded.

With this terminology, the above definition of the lexicographical order becomes more concise: Given a [[Partial order|partially]] or [[total order|totally ordered]] set {{math|''A''}}, and two words {{math|''a''}} and {{math|''b''}} over {{math|''A''}} such that {{math|''b''}} is non-empty, then one has {{math|''a'' < ''b''}} under lexicographical order, if at least one of the following conditions is satisfied:

* {{math|''a''}} is a prefix of {{math|''b''}}
* there exists words {{math|''u''}}, {{math|''v''}}, {{math|''w''}} (possibly empty) and elements {{math|''x''}} and {{math|''y''}} of {{math|''A''}} such that
::{{math|''x'' < ''y''}}
::{{math|1=''a'' = ''uxv''}}
::{{math|1=''b'' = ''uyw''}}

Notice that, due to the prefix condition in this definition, <math>\varepsilon < b\,\, \text{ for all } b \neq \varepsilon,</math> where <math>\varepsilon</math> is the empty word.

If <math>\,<\,</math> is a total order on <math>A,</math> then so is the lexicographic order on the words of <math>A.</math> However, in general this is not a [[well-order]], even if the alphabet <math>A</math> is well-ordered. For instance, if {{math|1=''A'' = {''a'', ''b''}{{void}}}}, the [[Formal language|language]] {{math|{''a''<sup>''n''</sup>''b'' {{!}} ''n'' ≥ 0, ''b'' > ''ε''}{{void}}}} has no least element in the lexicographical order: {{math|... < ''aab'' < ''ab'' < ''b''}}.

Since many applications require well orders, a variant of the lexicographical orders is often used. This well-order, sometimes called {{em|[[shortlex]]}} or {{em|quasi-lexicographical order}}, consists in considering first the lengths of the words (if {{math|length(''a'') < length(''b'')}}, then <math>a < b</math>), and, if the lengths are equal, using the lexicographical order. If the order on {{math|''A''}} is a well-order, the same is true for the shortlex order.<ref name="BaaderNipkow1999"/><ref>{{cite book | last=Calude | first=Cristian | author-link=Cristian S. Calude | title=Information and randomness. An algorithmic perspective | url=https://archive.org/details/informationrando00calu_163 | url-access=limited | series=[[EATCS]] Monographs on Theoretical Computer Science | publisher=[[Springer-Verlag]] | year=1994 | isbn=3-540-57456-5 | zbl=0922.68073 | page=[https://archive.org/details/informationrando00calu_163/page/n19 1] }}</ref>