Автоматическая последовательность

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

Автоматический набор представляет собой набор неотрицательных целых чисел S , для которых последовательность значений его характеристической функции х _S представляет собой автоматическую последовательность; то есть S является k -автоматическим, если χ _S ( n ) является k -автоматическим, где χ _S ( n ) = 1, если n  S, и 0 в противном случае. ^{[3] [4]}${\ displaystyle \ in}$ 

Определение [ править ]

Автоматические последовательности могут быть определены несколькими способами, каждый из которых эквивалентен. Ниже приведены четыре общих определения.

Теоретико-автоматные [ править ]

Пусть k - натуральное число , и пусть D = ( Q , Σ _k , δ, q ₀ , ∆, τ) - детерминированный конечный автомат с выходом , где

• Q представляет собой конечное множество состояний;
• входной алфавит Σ _K состоит из множества {0,1, ..., к -1} возможных цифр в базе - K обозначений;
• δ: Q × Σ _k → Q - функция перехода;
• д ₀ ∈ Q является начальным состоянием;
• выходной алфавит Δ - конечное множество; и
• τ: Q → Δ - отображение выходной функции из множества внутренних состояний в выходной алфавит.

Расширьте функцию перехода δ от воздействия на одиночные цифры к действию на строки цифр, определив действие δ на строку s, состоящую из цифр s ₁ s ₂ ... s _t, как:

δ ( q , s ) = δ (δ ( q ₀ , s ₁ s ₂ ... s _{t -1} ), s _t ).

Определите функцию a из набора натуральных чисел в выходной алфавит Δ следующим образом:

a ( n ) = τ (δ ( q ₀ , s ( n ))),

где s ( n ) - это n, записанное по основанию k . Тогда последовательность a = a (1) a (2) a (3) ... является k -автоматической последовательностью. ^[1]

Автомат, считывающий базовые k цифр s ( n ), начиная со старшего разряда, называется прямым чтением , а автомат, начинающийся с младшего разряда, - обратным чтением . ^[4] Приведенное выше определение справедливо независимо от того, является ли s ( n ) прямым или обратным чтением. ^[5]

Замена [ править ]

Пусть быть K - равномерный морфизм из в свободном моноиде и пусть будет кодирования (то есть -равномерная морфизм), как и в автоматах теоретико-случае. Если это фиксированная точка из , то есть, если -Затем является к -автоматической последовательности. ^[6] Наоборот, таким способом можно получить любую k -автоматическую последовательность. ^[4] Этот результат принадлежит Кобхэму, и в литературе он упоминается как маленькая теорема Кобэма . ^{[2] [7]}${\ displaystyle \ varphi}$ ${\ displaystyle \ Sigma ^ {*}}$${\ Displaystyle \ тау}$${\ displaystyle 1}$${\ displaystyle w}$${\ displaystyle \ varphi}$${\ Displaystyle ш = \ varphi (ш)}$${\ Displaystyle s = \ тау (ш)}$

k- ядро [ править ]

Пусть k  ≥ 2. k-ядром последовательности s ( n ) называется множество подпоследовательностей

${\displaystyle K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}$

В большинстве случаев k- ядро последовательности бесконечно. Однако, если k -ядро конечно, то последовательность s ( n ) k -автоматична, и верно и обратное. Это связано с Айленбергом. ^{[8] [9] [10]}

Отсюда следует, что k -автоматическая последовательность обязательно является последовательностью в конечном алфавите.

Формальный степенной ряд [ править ]

Пусть u ( n ) - последовательность над алфавитом Σ, и предположим, что существует инъективная функция β из Σ в конечное поле F _q , где q = p ⁿ для некоторого простого числа p . Ассоциированный формальный степенной ряд является

${\displaystyle \sum _{i\geq 0}\beta (u(i))X^{i}.}$

Тогда последовательность u является q -автоматической тогда и только тогда, когда этот формальный степенной ряд алгебраичен над F _q ( X ). Этот результат принадлежит Кристолу, и в литературе он упоминается как теорема Кристола . ^[11]

История [ править ]

Автоматические последовательности были введены Бючи в 1960 году ^[12], хотя в его статье использовался более логико-теоретический подход к этому вопросу и не использовалась терминология, найденная в этой статье. Понятие автоматических последовательностей было дополнительно изучено Кобхэмом в 1972 году, который назвал эти последовательности «последовательностями унифицированных тегов ». ^[7]

Термин «автоматическая последовательность» впервые появился в работе Deshouillers. ^[13]

Примеры [ править ]

Следующие последовательности выполняются автоматически:

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

Последовательность Туэ – Морса t ( n ) ( OEIS :  A010060 ) является неподвижной точкой морфизма 0 → 01, 1 → 10. Поскольку n-й член последовательности Туэ – Морса считает количество единиц по модулю 2 в база-2 представление п , оно порождается двумя состояниями детерминированного конечного автомата с выходом , изображенные здесь, где будучи в состоянии д ₀ указывает на то есть четное число единиц в представлении п и быть в состоянии д ₁ показывает , что существует нечетное количество единиц. Следовательно, последовательность Туэ – Морса 2-автоматна.

Последовательность удвоения периода [ править ]

П -й срок удвоения периода последовательности г ( п ) ( OEIS :  A096268 ) определяется соотношением экспоненты наивысшей степени 2 , делящей п . Это также неподвижная точка морфизма 0 → 01, 1 → 00. ^[14] Начиная с начального члена w = 0 и повторяя 2-равномерный морфизм φ на w, где φ (0) = 01 и φ (1) = 00, очевидно, что последовательность удвоения периода является фиксированной точкой функции φ ( w ) и, следовательно, является 2-автоматической.

Последовательность Рудина – Шапиро [ править ]

П -й член последовательности Рудина-Шапиро г ( п ) ( OEIS :  A020985 ) определяется числом последовательных единиц в представлении базы-2 н . 2-ядро последовательности Рудина – Шапиро ^[15] есть

${\displaystyle {\begin{aligned}r(2n)&=r(n),\\r(4n+1)&=r(n),\\r(8n+7)&=r(2n+1),\\r(16n+3)&=r(8n+3),\\r(16n+11)&=r(4n+3).\end{aligned}}}$

Поскольку 2-ядро состоит только из r ( n ), r (2 n  + 1), r (4 n  + 3) и r (8 n  + 3), оно конечно и, следовательно, последовательность Рудина – Шапиро равна 2 -автоматический.

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

Как последовательность Баума – Свита ^[16] ( OEIS :  A086747 ), так и обычная последовательность складывания бумаги ^{[17] [18] [19]} ( OEIS :  A014577 ) выполняются автоматически. Кроме того, автоматически выполняется обычная последовательность складывания бумаги с периодической последовательностью складок. ^[20]

Свойства [ править ]

Автоматические последовательности обладают рядом интересных свойств. Неисчерпывающий список этих свойств представлен ниже.

• Каждая автоматическая последовательность - это морфическое слово . ^[21]
• Для k  ≥ 2 и r  ≥ 1 последовательность является k -автоматической тогда и только тогда, когда она k ^r -автоматична. Этот результат принадлежит Эйленбергу. ^[22]
• Для мультипликативно независимых h и k последовательность является h -автоматической и k -автоматической тогда и только тогда, когда она в конечном итоге периодична. ^[23] Этот результат принадлежит Кобхэму, ^[24] с многомерным обобщением, принадлежащим Семенову. ^{[25] [26]}
• Если u ( n ) - k -автоматическая последовательность над алфавитом Σ, а f - равномерный морфизм из Σ ^∗ в другой алфавит ∆ ^∗ , то f ( u ) - k -автоматическая последовательность над ∆. ^[27]
• Если u ( n ) является k -автоматической последовательностью, то последовательности u ( k ⁿ ) и u ( k ⁿ  - 1) в конечном итоге периодичны. ^[28] И наоборот, если u ( n ) является предельно периодической последовательностью, то последовательность v, определенная как v ( k ⁿ ) = u ( n ), а в противном случае ноль является k -автоматической. ^[29]

Доказательство и опровержение автоматизма [ править ]

Учитывая последовательность-кандидат , обычно легче опровергнуть ее автоматичность, чем доказать. С помощью k -ядерной характеризации k -автоматических последовательностей достаточно создать бесконечно много различных элементов в k- ядре, чтобы показать, что это не k -автоматическая последовательность. Эвристически можно попытаться доказать автоматичность, проверив согласование терминов в k- ядре, но иногда это может приводить к неверным предположениям. Например, пусть ${\displaystyle s=(s_{n})_{n\geq 0}}$${\displaystyle K_{k}(s)}$${\displaystyle s}$

${\displaystyle t=011010011\dots }$

быть словом Туэ – Морзе. Позвольте быть словом, полученным путем конкатенации последовательных терминов в последовательности длин серий . Затем начинается${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$

${\displaystyle s=12112221\dots .}$.

Известно, что неподвижная точка морфизма${\displaystyle s}$${\displaystyle h^{\omega }(1)}$

${\displaystyle h(1)=121,h(2)=12221.}$

Это слово не является 2-автоматным, но некоторые элементы его 2-ядра совпадают для многих терминов. Например,${\displaystyle s}$${\displaystyle s_{16n+1}=s_{64n+1}{\text{ for }}0\leq n\leq 1864134}$

но не для . ^[30]${\displaystyle n=1864135}$

Если предположить, что последовательность автоматическая, есть несколько полезных подходов к ее доказательству. Один из подходов состоит в том, чтобы напрямую построить детерминированный автомат с выходом, который дает последовательность. Пусть написано в алфавите , и пусть обозначает базовое расширение . Тогда последовательность является -автоматической тогда и только тогда, когда каждый из слоев${\displaystyle (s_{n})_{n\geq 0}}$${\displaystyle \Delta }$${\displaystyle (n)_{k}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle s=(s_{n})_{n\geq 0}}$${\displaystyle k}$

${\displaystyle I_{k}(s,d):=\{(n)_{k}\mid s_{n}=d\}}$

это обычный язык. ^[31] Проверить регулярность слоев часто можно с помощью леммы о накачке для регулярных языков .

Если обозначает сумму цифр в разложении по основанию и является многочленом с неотрицательными целыми коэффициентами, а если , являются целыми числами, то последовательность${\displaystyle s_{k}(n)}$${\displaystyle k}$${\displaystyle n}$${\displaystyle p(X)}$${\displaystyle k\geq 2}$${\displaystyle m\geq 1}$

${\displaystyle (s_{k}(p(n)){\pmod {m}})_{n\geq 0}}$

является -автоматическим тогда и только тогда , когда либо . ^[32]${\displaystyle k}$${\displaystyle \deg p\leq 1}$${\displaystyle m\mid k-1}$

1-автоматические последовательности [ править ]

k -автоматические последовательности обычно определяются только для k  ≥ 2. ^[1] Концепция может быть расширена до k = 1 путем определения 1-автоматической последовательности как последовательности, n-й член которой зависит от унарной записи для n ; то есть (1) ⁿ . Поскольку конечный автомат должен в конечном итоге вернуться в ранее посещенное состояние, все 1-автоматические последовательности в конечном итоге являются периодическими.

Обобщения [ править ]

Автоматические последовательности устойчивы к изменениям как в определении, так и во входной последовательности. Например, как отмечено в теоретико-автоматном определении, данная последовательность остается автоматической как при прямом, так и при обратном чтении входной последовательности. Последовательность также остается автоматической, когда используется альтернативный набор цифр или когда основание инвертируется; то есть, когда входная последовательность представлена ​​в базе - k, а не в базе k . ^[33] Однако, в отличие от использования альтернативного набора цифр, смена основания может повлиять на автоматичность последовательности.

Область автоматической последовательности может быть расширена с натуральных чисел до целых с помощью двусторонних автоматических последовательностей. Это связано с тем, что при k  ≥ 2 каждое целое число может быть однозначно представлено в виде где . Тогда двусторонняя бесконечная последовательность a ( n ) _n является (- k ) -автоматической тогда и только тогда, когда ее подпоследовательности a ( n ) _{n ≥ 0} и a (- n ) _{n ≥ 0} являются k -автоматическими. ^[34]${\displaystyle \sum _{0\leq i\leq r}a_{i}(-k)^{i},}$${\displaystyle a_{i}\in \{0,\dots ,k-1\}}$ _{${\displaystyle \in \mathbb {Z} }$}

Алфавит k -автоматической последовательности можно расширить с конечного размера до бесконечного с помощью k -регулярных последовательностей . ^[35] K -регулярных последовательность может быть охарактеризована как те последовательности , у которых к -ядру конечно-порожденные. Всякая ограниченная k -регулярная последовательность автоматична. ^[36]

Логический подход [ править ]

Для многих 2 автоматических последовательностей , карта обладает свойством , что теория первого порядка является разрешимой . Поскольку многие нетривиальные свойства автоматических последовательностей могут быть записаны в логике первого порядка, эти свойства можно доказать механически, выполнив процедуру принятия решения. ^[37]${\displaystyle s=(s_{n})_{n\geq 0}}$${\displaystyle n\mapsto s_{n}}$${\displaystyle {\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})}$

Например, таким способом можно механически проверить следующие свойства слова Туэ – Морса:

• Слово Туэ – Морса не имеет перекрытий, т. Е. Не содержит слова в форме где - одна буква и, возможно, является пустым словом.${\displaystyle cxcxc}$${\displaystyle c}$${\displaystyle w}$
• Непустое слово выделяется рамкой, если есть непустое слово и, возможно, пустое слово с . Слово Туэ – Морса содержит множитель с границами для каждой длины, превышающей 1. ^[38]${\displaystyle x}$${\displaystyle w}$${\displaystyle y}$${\displaystyle x=wyw}$
• В слове Туэ – Морса есть множитель длины без рамки тогда и только тогда, когда где обозначает двоичное представление . ^[39]${\displaystyle n}$${\displaystyle (n)_{2}\notin 1(01^{*}0)^{*}10^{*}1}$${\displaystyle (n)_{2}}$${\displaystyle n}$

Программное обеспечение Walnut ^{[40] [41],} разработанное Хамоном Мусави, реализует процедуру принятия решения для определения многих свойств определенных автоматических слов, таких как слово Туэ – Морзе. Эта реализация является следствием вышеупомянутой работы над логическим подходом к автоматическим последовательностям.

См. Также [ править ]

• Бюхи арифметика

Заметки [ править ]

Ссылки [ править ]

• Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6. Zbl  1086.11015 .
• Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и их повторы . Серия монографий CRM. 27 . Провиденс, Род-Айленд: Американское математическое общество . ISBN 978-0-8218-4480-9. Zbl  1161.68043 .
• Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. 137 . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-19022-0. Zbl  1250,68007 .
• Кобэм, Алан (1972). «Единые последовательности тегов». Математика. Теория систем . 6 (1–2): 164–192. DOI : 10.1007 / BF01706087 .
• Лотэр, М. (2005). Прикладная комбинаторика слов . Энциклопедия математики и ее приложений. 105 . Коллективный труд Жан Berstel Доминик Перрен, Максим Крошемор, Эрик Лапорта, Меряр Мори, Надя Pisanti, Мари-Франс Sagot, Гезине Рейнертом , Софи Schbath , Майкл Waterman, Филипп Жаке, Войцех Szpankowski , Доминик Poulalhon, Жиль Шеффера, Роман Колпаков , Грегори Кушеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-84802-2. Zbl  1133.68067 .
• Пифей Фогг, Н. (2002). Подстановки в динамике, арифметике и комбинаторике . Конспект лекций по математике. 1794 . Редакторы Берте, Валери ; Ференци, Себастьен; Mauduit, Christian; Зигель, А. Берлин: Springer-Verlag . ISBN 978-3-540-44141-0. Zbl  1014.11015 .

Дальнейшее чтение [ править ]

• Берте, Валери; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. 135 . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-51597-9. Zbl  1197.68006 .
• Локстон, Дж. Х (1988). «13. Автоматы и трансцендентность». В Бейкер, А. (ред.). Новые достижения в теории трансцендентности . Издательство Кембриджского университета . стр.  215 -228. ISBN 978-0-521-33545-4. Zbl  0656.10032 .
• Роуленд, Эрик (2015), «Что такое ... автоматическая последовательность?», Уведомления Американского математического общества , 62 (3): 274–276, doi : 10.1090 / noti1218.
• Шаллит, Джеффри (1999). «Теория чисел и формальные языки». In Hejhal, Dennis A .; Фридман, Джоэл; Гуцвиллер, Мартин К .; Одлызко, Эндрю М. (ред.). Новые приложения теории чисел. На основе трудов летней программы IMA, Миннеаполис, штат Миннесота, США, июль 15-26, 1996 . Объемы IMA по математике и ее приложениям. 109 . Springer-Verlag . С. 547–570. ISBN 978-0-387-98824-5.