In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, and particularly in the theory of
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sym ...
s, shortlex is a
total ordering for
finite sequences of objects that can themselves be totally ordered. In the shortlex ordering, sequences are primarily sorted by
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
(length) with the shortest sequences first, and sequences of the same length are sorted into
lexicographical order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...
. Shortlex ordering is also called radix, length-lexicographic, military, or genealogical ordering.
In the context of
strings on a totally ordered alphabet, the shortlex order is identical to the lexicographical order, except that shorter strings precede longer strings. For example, the shortlex order of the set of strings on the English alphabet (in its usual order) is
'ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa, aab, aac, ..., zzz, ...'' where ε denotes the
empty string
In formal language theory, the empty string, or empty word, is the unique string of length zero.
Formal theory
Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special c ...
.
The strings in this ordering over a fixed finite alphabet can be placed into one-to-one order-preserving correspondence with the non-negative
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s, giving the
bijective numeration system for representing numbers. The shortlex ordering is also important in the theory of
automatic groups.
[.]
See also
*
Graded lexicographic order
References
Order theory
{{algebra-stub