В математике , и в частности , в теории формальных языков , shortlex является общим упорядочением для конечных последовательностей объектов , которые сами по себе могут быть вполне упорядочены. При упорядочении коротких строк последовательности в первую очередь сортируются по мощности (длине), причем сначала самые короткие последовательности, а последовательности одинаковой длины сортируются в лексикографическом порядке . [1] Упорядочение коротких строк также называется основанием , лексикографическим , военным или генеалогическим порядком. [2]
В контексте строк на упорядоченный алфавите, то shortlex порядок идентичен лексикографический порядок, за исключением того, что короткие строки предшествуют более длинные строки. Например, порядок коротких строк набора строк в английском алфавите (в обычном порядке) равен [ ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa , aab, aac, ..., zzz, ... ], где ε обозначает пустую строку .
Строки в этом порядке в фиксированном конечном алфавите могут быть помещены во взаимно однозначное соответствие с неотрицательными целыми числами , что дает биективную систему счисления для представления чисел. [3] Порядок коротких замыканий также важен в теории автоматических групп . [4]
Рекомендации
- ^ Сипсер, Майкл (2012). Введение в теорию вычислений (3-е изд.). Бостон, Массачусетс: Cengage Learning. п. 14 . ISBN 978-1133187790.
- ^ Барань, Винс (2008), "Иерархия автоматических со-слова , имеющие разрешимую теорию MSO", RAIRO Теоретическая информатика и приложение , 42 (3): 417-450, DOI : 10,1051 / ит: 2008008 , MR 2434027.
- ^ Smullyan, R. (1961), «9. Лексикографическое упорядочение; n -адическое представление целых чисел» , Теория формальных систем , Annals of Mathematics Studies, 47 , Princeton University Press, стр. 34–36..
- ^ Эпштейн, Дэвид Б.А .; Кэннон, Джеймс У .; Холт, Дерек Ф .; Леви, Сильвио В.Ф .; Патерсон, Майкл С .; Терстон, Уильям П. (1992), Обработка текста в группах , Бостон, Массачусетс: Jones and Bartlett Publishers, стр. 56, ISBN 0-86720-244-0, Руководство по ремонту 1161694.