WikiDer > K-регулярная последовательность

K-regular sequence

В математика и теоретическая информатика, а k-регулярная последовательность это последовательность удовлетворяющие линейным рекуррентным уравнениям, отражающим основание-k представления целых чисел. Класс k-регулярные последовательности обобщают класс k-автоматические последовательности в алфавиты бесконечного размера.

Определение

Существует несколько характеристик k-регулярные последовательности, все из которых эквивалентны. Ниже приведены некоторые общие характеристики. Для каждого берем р' быть коммутативный Кольцо Нётериана и мы берем р быть звенеть содержащий р′.

k-ядро

Позволять k ≥ 2. k-ядро последовательности это множество подпоследовательностей

Последовательность является (р′, k) -регулярный (часто сокращается до "k-регулярный "), если -модуль, созданный Kk(s) это конечно порожденный р′-модуль.[1]

В частном случае, когда , последовательность является -регулярно, если содержится в конечномерном векторном пространстве над .

Линейные комбинации

Последовательность s(п) является k-регулярно, если существует целое число E такое, что для всех еj > E и 0 ≤ рjkеj - 1, каждая подпоследовательность s формы s(kеjп + рj) выражается как р′-линейная комбинация , куда cij целое число, жijE, и 0 ≤ бijkжij − 1.[2]

В качестве альтернативы последовательность s(п) является k-регулярно, если существует целое число р и подпоследовательности s1(п), ..., sр(п) такое, что для всех 1 ≤ яр и 0 ≤ аk - 1, каждая последовательность sя(кн + а) в k-ядро Kk(s) является р′ -Линейная комбинация подпоследовательностей sя(п).[2]

Формальная серия

Позволять Икс0, ..., Иксk − 1 быть набором k некоммутирующие переменные, и пусть τ - отображение, отправляющее некоторое натуральное число п к строке Икса0 ... Иксае − 1, где база-k представление Икс это строка ае − 1...а0. Тогда последовательность s(п) является k-регулярно тогда и только тогда, когда формальная серия является -рациональный.[3]

Теоретико-автоматные

Определение формального ряда k-регулярная последовательность приводит к характеристике автомата, подобной SchützenbergerМатричная машина.[4][5]

История

Понятие k-регулярные последовательности впервые были исследованы в паре работ Аллуша и Шаллита.[6] До этого Берстель и Ройтенауэр изучали теорию рациональный ряд, который тесно связан с k-регулярные последовательности.[7]

Примеры

Последовательность линейки

Позволять быть -адическая оценка из . Последовательность линейки (OEISA007814) является -регулярный, а -ядро

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

которое вместе с начальными условиями и , однозначно определяют последовательность.[8]

Последовательность Туэ – Морса

В Последовательность Туэ – Морса т(п) (OEISA010060) это фиксированная точка морфизма 0 → 01, 1 → 10. Известно, что последовательность Туэ – Морса 2-автоматна. Таким образом, он также 2-регулярен, и его 2-ядро

состоит из подпоследовательностей и .

Числа Кантора

Последовательность Числа Кантора c(п) (OEISA005823) состоит из чисел, тройной расширения не содержат единиц. Несложно показать, что

и, следовательно, последовательность чисел Кантора 2-регулярна. Аналогичным образом Последовательность Стэнли

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (последовательность A005836 в OEIS)

чисел, тернарные разложения которых не содержат двоек, также 2-регулярны.[9]

Сортировка чисел

Несколько интересное приложение понятия k-регулярность к более широкому изучению алгоритмов обнаруживается при анализе Сортировка слиянием алгоритм. Учитывая список п значений, количество сравнений, сделанных алгоритмом сортировки слиянием, является сортировка чисел, управляемый рекуррентным соотношением

В результате последовательность, определяемая рекуррентным соотношением для сортировки слиянием, Т(п), составляет 2-регулярную последовательность.[10]

Другие последовательности

Если является целочисленный многочлен, тогда является k-регулярно для каждого .

В Глейшер-Гулд последовательность 2-регулярная. Последовательность Штерна – Броко 2-регулярна.

Аллуш и Шаллит приводят ряд дополнительных примеров k-регулярные последовательности в своих работах.[6]

Характеристики

k-регулярные последовательности обладают рядом интересных свойств.

  • Каждый k-автоматическая последовательность является k-обычный.[11]
  • Каждый k-синхронизированная последовательность является k-обычный.
  • А k-регулярная последовательность принимает конечное число значений тогда и только тогда, когда она k-автоматический.[12] Это непосредственное следствие класса k-регулярные последовательности, являющиеся обобщением класса k-автоматические последовательности.
  • Класс k-регулярные последовательности замкнуты относительно почленного сложения, почленного умножения и свертка. Класс k-регулярные последовательности также замыкаются при масштабировании каждого члена последовательности на целое число λ.[12][13][14][15] В частности, набор k-регулярный степенной ряд образует кольцо.[16]
  • Если является k-регулярно, то для всех целых чисел , является k-автоматический. Однако обратное неверно.[17]
  • Для мультипликативно независимых kл ≥ 2, если последовательность k-регулярные и л-регулярна, то последовательность удовлетворяет линейной рекуррентности.[18] Это обобщение результата Кобэма относительно последовательностей, которые являются k-автоматический и л-автоматический.[19]
  • В п-й срок k-регулярная последовательность целых чисел растет не более чем полиномиально за п.[20]
  • Если это поле и , то последовательность степеней является k-регулярно тогда и только тогда, когда или же является корнем единства.[21]

Доказательство и опровержение k-регулярность

Учитывая последовательность кандидатов это не известно k-обычный, k-регулярность обычно может быть доказана непосредственно из определения путем вычисления элементов ядра и доказывая, что все элементы формы с достаточно большой и можно записать в виде линейных комбинаций элементов ядра с меньшими показателями вместо . Обычно это просто с вычислительной точки зрения.

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

Позволять обозначить количество в двоичном разложении . Позволять обозначить количество в двоичном разложении . Последовательность может быть 2-регулярным. Последовательность однако не является 2-регулярным по следующему аргументу. Предполагать 2-регулярный. Мы утверждаем, что элементы за и 2-ядра линейно независимы над . Функция сюръективен на целые числа, поэтому пусть - наименьшее целое число такое, что . По 2-регулярности , существуют и константы так что для каждого ,

Позволять быть наименьшим значением, для которого . Тогда для каждого ,

Оценивая это выражение в , куда и так далее, в левой части получим

а с правой стороны

Отсюда следует, что для любого целого числа ,

Но для , правая часть уравнения монотонна, поскольку имеет вид для некоторых констант , а левая - нет, что можно проверить, последовательно подключив , , и . Следовательно, не является 2-регулярным.[22]

Примечания

  1. ^ Аллуш и Шаллит (1992), определение 2.1.
  2. ^ а б Аллуш и Шаллит (1992), теорема 2.2.
  3. ^ Аллуш и Шаллит (1992), теорема 4.3.
  4. ^ Аллуш и Шаллит (1992), теорема 4.4.
  5. ^ Шютценбергер, М.-П. (1961), «Об определении семейства автоматов», Информация и контроль, 4 (2–3): 245–270, Дои:10.1016 / S0019-9958 (61) 80020-X.
  6. ^ а б Аллуш и Шаллит (1992, 2003).
  7. ^ Берстель, Жан; Ройтенауэр, Кристоф (1988). Рациональные серии и их языки. Монографии EATCS по теоретической информатике. 12. Springer-Verlag. ISBN 978-3-642-73237-9.
  8. ^ Allouche & Shallit (1992), пример 8.
  9. ^ Allouche & Shallit (1992), примеры 3 и 26.
  10. ^ Allouche & Shallit (1992), пример 28.
  11. ^ Аллуш и Шаллит (1992), теорема 2.3.
  12. ^ а б Allouche & Shallit (2003) стр. 441.
  13. ^ Аллуш и Шаллит (1992), теорема 2.5.
  14. ^ Аллуш и Шаллит (1992), теорема 3.1.
  15. ^ Allouche & Shallit (2003) стр. 445.
  16. ^ Аллуш и Шаллит (2003) стр. 446.
  17. ^ Аллуш и Шаллит (2003) стр. 441.
  18. ^ Белл, Дж. (2006). «Обобщение теоремы Кобэма для регулярных последовательностей». Séminaire Lotharingien de Combinatoire. 54A.
  19. ^ Кобхэм, А. (1969). «О базисной зависимости множеств чисел, распознаваемых конечными автоматами». Математика. Теория систем. 3 (2): 186–192. Дои:10.1007 / BF01746527.
  20. ^ Allouche & Shallit (1992) Теорема 2.10.
  21. ^ Аллуш и Шаллит (2003) стр. 444.
  22. ^ Аллуш и Шаллит (1993) стр. 168–169.

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