В математике и теоретической информатике , к -регулярна последовательностью является последовательностью , удовлетворяющей линейных рекуррентных уравнений , которые отражают base- K представление целых чисел. Класс k -регулярных последовательностей обобщает класс k -автоматических последовательностей на алфавиты бесконечного размера.
Определение
Существует несколько характеризаций k -регулярных последовательностей, все из которых эквивалентны. Вот некоторые общие характеристики. Для каждого из них мы возьмем R ′ как коммутативное нётерово кольцо и возьмем R как кольцо, содержащее R ′.
к -kernel
Пусть k ≥ 2. k-ядро последовательности это множество подпоследовательностей
Последовательность является ( R ′, k ) -регулярным (часто сокращается до просто « k -регулярным»), если-модуль, порожденный K k ( s ), является конечно порожденным R ′ - модулем . [1]
В частном случае, когда , последовательность является -регулярно, если содержится в конечномерном векторном пространстве над .
Линейные комбинации
Последовательность s ( n ) является k -регулярной, если существует такое целое число E , что для всех e j > E и 0 ≤ r j ≤ k e j - 1 каждая подпоследовательность s вида s ( k e j n + r j ) выражается как R ′ - линейная комбинация , где c ij - целое число, f ij ≤ E и 0 ≤ b ij ≤ k f ij - 1. [2]
В качестве альтернативы последовательность s ( n ) является k -регулярной, если существует целое число r и подпоследовательности s 1 ( n ), ..., s r ( n ) такие, что для всех 1 ≤ i ≤ r и 0 ≤ a ≤ k - 1, каждая последовательность s i ( kn + a ) в k -ядре K k ( s ) является R ′ -линейной комбинацией подпоследовательностей s i ( n ). [2]
Формальная серия
Пусть x 0 , ..., x k - 1 - набор из k некоммутирующих переменных, а τ - карта, отправляющая некоторое натуральное число n в строку x a 0 ... x a e - 1 , где основание - k представление x - это строка a e - 1 ... a 0 . Тогда последовательность s ( n ) k -регулярна тогда и только тогда, когда формальный ряд является - рационально . [3]
Теоретико-автоматные
Формальный ряд определение а K -регулярной приводит к последовательности автомата , подобной характеристике Шютценберж матрицы машине «ы. [4] [5]
История
Понятие k -регулярных последовательностей впервые было исследовано в паре статей Аллуша и Шаллита. [6] До этого Берстель и Ройтенауэр изучали теорию рациональных рядов , которая тесно связана с k -регулярными последовательностями. [7]
Примеры
Последовательность линейки
Позволять быть -адическая оценка из. Последовательность линейки( OEIS : A007814 ) - это-регулярный, а -ядро
содержится в двумерном векторном пространстве, порожденном и постоянная последовательность . Эти базисные элементы приводят к рекуррентным соотношениям
которое вместе с начальными условиями а также , однозначно определяют последовательность. [8]
Последовательность Туэ – Морса
Последовательность Туэ – Морса t ( n ) ( OEIS : A010060 ) является неподвижной точкой морфизма 0 → 01, 1 → 10. Известно, что последовательность Туэ – Морса является 2-автоматической. Таким образом, он также является 2-регулярным, и его 2-ядро
состоит из подпоследовательностей а также .
Числа Кантора
Последовательность чисел Кантора c ( n ) ( OEIS : A005823 ) состоит из чисел, троичные разложения которых не содержат единиц. Несложно показать, что
и поэтому последовательность чисел Кантора 2-регулярна. Аналогично последовательность Стэнли
чисел, тернарные разложения которых не содержат двоек, также 2-регулярны. [9]
Сортировка чисел
Несколько интересное применение понятия k -регулярности к более широкому изучению алгоритмов можно найти при анализе алгоритма сортировки слиянием . Учитывая список из n значений, количество сравнений, сделанных алгоритмом сортировки слиянием, является числами сортировки , управляемыми рекуррентным соотношением
В результате последовательность, определяемая рекуррентным соотношением для сортировки слиянием, T ( n ), составляет 2-регулярную последовательность. [10]
Другие последовательности
Если является целочисленным многочленом , тоявляется K -регулярна для каждого.
Последовательность Глейшера – Гулда 2-регулярна. Последовательность Штерна – Броко 2-регулярна.
Аллуш и Шаллит в своих работах приводят ряд дополнительных примеров k -регулярных последовательностей. [6]
Характеристики
k -регулярные последовательности обладают рядом интересных свойств.
- Каждая к -автоматической последовательности является K -регулярны. [11]
- Каждый к -synchronized последовательности есть к -регулярна.
- К -регулярна последовательности принимает конечное число значений , если и только если K -автоматическими. [12] Это непосредственное следствие того, что класс k -регулярных последовательностей является обобщением класса k -автоматических последовательностей.
- Класс k -регулярных последовательностей замкнут относительно почленного сложения, почленного умножения и свертки . Класс k -регулярных последовательностей также замыкается при масштабировании каждого члена последовательности на целое число λ. [12] [13] [14] [15] В частности, множество k -регулярных степенных рядов образует кольцо. [16]
- Если является K -регулярна, то для всех целых чисел, является к -автоматическому. Однако обратное неверно. [17]
- Для мультипликативно независимых k , l ≥ 2, если последовательность одновременно k -регулярна и l -регулярна, то она удовлетворяет линейной рекуррентности. [18] Это обобщение результата Кобэма относительно последовательностей, которые являются как k -автоматическими, так и l -автоматическими. [19]
- П - й член в K -регулярной последовательности целых чисел растет наиболее Полиномиально в п . [20]
- Если это поле и , то последовательность степеней является к -регулярна тогда и только тогда , когда или же это корень единства. [21]
Доказательство и опровержение k -регулярности
Учитывая последовательность кандидатов который не известен как k -регулярность, k -регулярность обычно может быть доказана непосредственно из определения путем вычисления элементов ядра и доказывая, что все элементы формы с участием достаточно большой и можно записать в виде линейных комбинаций элементов ядра с меньшими показателями вместо . Обычно это несложно с вычислительной точки зрения.
С другой стороны, опровержение k -регулярности последовательности-кандидата обычно требуется один, чтобы произвести -линейно независимое подмножество в ядре , что обычно бывает сложнее. Вот один из примеров такого доказательства.
Позволять обозначить количество в двоичном разложении . Позволять обозначить количество в двоичном разложении . Последовательностьможно показать как 2-регулярный. Последовательностьоднако не является 2-регулярным по следующему аргументу. Предполагать2-регулярный. Мы утверждаем, что элементы для а также 2-ядра линейно независимы над . Функция сюръективен на целые числа, поэтому пусть - наименьшее целое число такое, что . По 2-регулярности, существуют и константы так что для каждого ,
Позволять быть наименьшим значением, для которого . Тогда для каждого,
Оценивая это выражение в , где и так далее, в левой части получим
а с правой стороны
Отсюда следует, что для любого целого числа ,
Но для , правая часть уравнения монотонна, поскольку имеет вид для некоторых констант , а левая - нет, что можно проверить, последовательно подключив , , а также . Следовательно,не является 2-регулярным. [22]
Заметки
- ^ Allouche и Shallit (1992), определение 2.1.
- ^ a b Allouche & Shallit (1992), теорема 2.2.
- ^ Allouche & Shallit (1992), теорема 4.3.
- ^ Allouche & Shallit (1992), теорема 4.4.
- ^ Шютценбергер, М.-П. (1961), "Об определении семейства автоматов", информации и управления , 4 (2-3): 245-270, DOI : 10.1016 / S0019-9958 (61) 80020-X.
- ^ a b Allouche & Shallit (1992, 2003).
- ^ Берстель, Жан; Ройтенауэр, Кристоф (1988). Рациональные серии и их языки . Монографии EATCS по теоретической информатике. 12 . Springer-Verlag . ISBN 978-3-642-73237-9.
- ^ Allouche & Shallit (1992), пример 8.
- ^ Allouche & Shallit (1992), примеры 3 и 26.
- ^ Allouche & Shallit (1992), Пример 28.
- ^ Allouche & Shallit (1992), теорема 2.3.
- ^ a b Allouche & Shallit (2003) стр. 441.
- ^ Allouche & Shallit (1992), теорема 2.5.
- ^ Allouche & Shallit (1992), теорема 3.1.
- ^ Allouche & Shallit (2003) стр. 445.
- ^ Allouche и Shallit (2003) стр. 446.
- ^ Allouche и Shallit (2003) стр. 441.
- ^ Белл, Дж. (2006). «Обобщение теоремы Кобэма для регулярных последовательностей». Séminaire Lotharingien de Combinatoire . 54А .
- ^ Кобхэм, А. (1969). «О базисной зависимости множеств чисел, распознаваемых конечными автоматами». Математика. Теория систем . 3 (2): 186–192. DOI : 10.1007 / BF01746527 .
- ^ Allouche & Shallit (1992) Теорема 2.10.
- ^ Allouche и Shallit (2003) стр. 444.
- ^ Allouche и Shallit (1993) р. 168–169.
Рекомендации
- Аллуш, Жан-Поль; Шаллит, Джеффри (1992), "Кольцо k -регулярных последовательностей", Теорет. Comput. Sci. , 98 (2): 163-197, DOI : 10.1016 / 0304-3975 (92) 90001-V.
- Аллуш, Жан-Поль; Шаллит, Джеффри (2003), "Кольцо k -регулярных последовательностей, II", Теорет. Comput. Sci. , 307 : 3-29, DOI : 10.1016 / s0304-3975 (03) 00090-2.
- Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6. Zbl 1086.11015 .