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

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

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

Эта алгеброй статья, связанная с , незавершена . Вы можете помочь Википедии, расширив ее .

[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 .

[1]

[2]

[3]

[4]