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.[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. E.g., 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 alphabet can be placed into one-to-one correspondence with the non-negative integers, giving the bijective numeration system for representing numbers.[3] The shortlex ordering is also important in the theory of automatic groups.[4]

References

  1. ↑ Sipser, Michael (2012). Introduction to the Theory of Computation (3 ed.). Boston, MA: Cengage Learning. p. 14. ISBN 978-1133187790.
  2. ↑ Bárány, Vince (2008), "A hierarchy of automatic ω-words having a decidable MSO theory", RAIRO Theoretical Informatics and Applications 42 (3): 417–450, doi:10.1051/ita:2008008, MR 2434027.
  3. ↑ Smullyan, R. (1961), "9. Lexicographical ordering; n-adic representation of integers", Theory of Formal Systems, Annals of Mathematics Studies 47, Princeton University Press, pp. 34–36.
  4. ↑ Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P. (1992), Word processing in groups, Boston, MA: Jones and Bartlett Publishers, p. 56, ISBN 0-86720-244-0, MR 1161694.


This article is issued from Wikipedia - version of the 6/7/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.