Shortlex order
In
lexicographical order.[1] Shortlex ordering is also called radix, length-lexicographic, military, or genealogical ordering.[2]
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.
The strings in this ordering over a fixed finite alphabet can be placed into one-to-one
order-preserving correspondence with the natural numbers, giving the bijective numeration system for representing numbers.[3] The shortlex ordering is also important in the theory of automatic groups.[4]
See also
References
- ISBN 978-1133187790.
- MR 2434027.
- ^ Smullyan, R. (1961), "9. Lexicographical ordering; n-adic representation of integers", Theory of Formal Systems, Annals of Mathematics Studies, vol. 47, Princeton University Press, pp. 34–36.
- MR 1161694.
 | This algebra-related article is a stub. You can help Wikipedia by expanding it. |