shortlex order
In mathematics, and particularly in the theory of formal languages, 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 (length) with the shortest sequences first, and sequences of the same length are sorted into lexicographical order.{{cite book
| last = Sipser | first = Michael | author-link = Michael Sipser
| isbn = 978-1133187790
| mr =
| page = [https://archive.org/details/introductiontoth00sips_872/page/n37 14]
| publisher = Cengage Learning
| location = Boston, MA
| title = Introduction to the Theory of Computation
| url = https://archive.org/details/introductiontoth00sips_872 | url-access = limited | year = 2012
| edition = 3}} Shortlex ordering is also called radix, length-lexicographic, military, or genealogical ordering.{{citation
| last = Bárány | first = Vince
| doi = 10.1051/ita:2008008
| issue = 3
| journal = RAIRO Theoretical Informatics and Applications
| mr = 2434027
| pages = 417–450
| title = A hierarchy of automatic ω-words having a decidable MSO theory
| volume = 42
| year = 2008}}.
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.{{citation
| last = Smullyan | first = R. | author-link = Raymond Smullyan
| contribution = 9. Lexicographical ordering; n-adic representation of integers
| contribution-url = https://books.google.com/books?id=O4wZLfMnd74C&pg=PA34
| pages = 34–36
| publisher = Princeton University Press
| series = Annals of Mathematics Studies
| title = Theory of Formal Systems
| volume = 47
| year = 1961}}. The shortlex ordering is also important in the theory of automatic groups.{{citation
| last1 = Epstein | first1 = David B. A. | author1-link = David B. A. Epstein
| last2 = Cannon | first2 = James W. | author2-link = James W. Cannon
| last3 = Holt | first3 = Derek F.
| last4 = Levy | first4 = Silvio V. F.
| last5 = Paterson | first5 = Michael S. | author5-link = Mike Paterson
| last6 = Thurston | first6 = William P. | author6-link = William Thurston
| isbn = 0-86720-244-0
| location = Boston, MA
| mr = 1161694
| page = 56
| publisher = Jones and Bartlett Publishers
| title = Word processing in groups
| title-link = Word Processing in Groups
| year = 1992}}.
