Короткий заказ

В математике , и в частности в теории формальных языков , shortlex — это полное упорядочение для конечных последовательностей объектов, которые сами могут быть полностью упорядочены. В упорядочении shortlex последовательности в первую очередь сортируются по мощности (длине), начиная с самых коротких последовательностей, а последовательности той же длины сортируются в лексикографическом порядке . ^[1] Упорядочение shortlex также называется радиксным , лексикографическим по длине , военным или генеалогическим упорядочением. ^[2]

В контексте строк в полностью упорядоченном алфавите порядок shortlex идентичен лексикографическому порядку, за исключением того, что более короткие строки предшествуют более длинным. Например, порядок shortlex набора строк в английском алфавите (в его обычном порядке) — [ ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa, aab, aac, ..., zzz, ... ], где ε обозначает пустую строку .

Строки в этом порядке над фиксированным конечным алфавитом могут быть помещены во взаимно-однозначное соответствие, сохраняющее порядок, с натуральными числами , что дает биективную систему нумерации для представления чисел. ^[3] Коротколексное упорядочение также важно в теории автоматических групп . ^[4]

Смотрите также

• Градуированный лексикографический порядок

Ссылки

1. Сипсер, Майкл (2012). Введение в теорию вычислений (3-е изд.). Бостон, Массачусетс: Cengage Learning. стр. 14. ISBN 978-1133187790.
2. Барани, Винс (2008), «Иерархия автоматических ω-слов, имеющих разрешимую теорию MSO», RAIRO Theoretical Informatics and Applications , 42 (3): 417–450, doi :10.1051/ita:2008008, MR  2434027.
3. Smullyan, R. (1961), "9. Лексикографическое упорядочение; n-адическое представление целых чисел", Теория формальных систем , Annals of Mathematics Studies, т. 47, Princeton University Press, стр. 34–36.
4. Эпштейн, Дэвид BA ; Кэннон, Джеймс У .; Холт, Дерек Ф.; Леви, Сильвио В.Ф.; Патерсон, Майкл С .; Терстон, Уильям П. (1992), Обработка текстов в группах , Бостон, Массачусетс: Jones and Bartlett Publishers, стр. 56, ISBN 0-86720-244-0, г-н  1161694.