Заказ шортлекс - Shortlex order

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

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

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

Рекомендации

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