Заказ шортлекса

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

В контексте строк полностью упорядоченного алфавита порядок коротких лексов идентичен лексикографическому порядку, за исключением того, что более короткие строки предшествуют более длинным строкам. Например, краткий порядок набора строк английского алфавита (в обычном порядке) такой: [ ε, 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. Смуллян, Р. (1961), «9. Лексикографическое упорядочение; n-адическое представление целых чисел», Теория формальных систем , Анналы математических исследований, том. 47, Princeton University Press, стр. 34–36..
4. Эпштейн, Дэвид Б.А .; Кэннон, Джеймс В .; Холт, Дерек Ф.; Леви, Сильвио В.Ф.; Патерсон, Майкл С .; Терстон, Уильям П. (1992), Обработка текста в группах , Бостон, Массачусетс: Jones and Bartlett Publishers, стр. 56, ISBN 0-86720-244-0, МР  1161694.