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

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

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

Определение

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

Теория автоматов

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

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

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

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

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

а ( п ) = τ(δ( q ₀ , s ( n ))),

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

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

Замена

Позволять $\varphi$ быть k - равномерным морфизмом свободного моноида $\Sigma ^{*}$ и пусть $\tau$ быть кодировкой (т. $1$-равномерный морфизм), как и в теоретико-автоматном случае. Если $w$ является фиксированной точкой $\varphi$- то есть, если $w=\varphi (w)$-затем $s=\tau (w)$ является k -автоматической последовательностью. любую k -автоматическую последовательность. И наоборот, таким способом можно получить Этот результат принадлежит Кобэму и в литературе называется малой теоремой Кобэма .

k -ядро

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

$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 -автоматической, и обратное также верно. Это заслуга Эйленберга.

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

степенной

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

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

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

История

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

Термин «автоматическая последовательность» впервые появился в статье Дешуйе.

Примеры

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

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

DFAO, генерирующий последовательность Туэ – Морса

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

периода

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

-

n - й член последовательности Рудина-Шапиро r ( n ) ( OEIS : A020985 ) определяется количеством последовательных единиц в представлении n по основанию 2 . 2-ядро последовательности Рудина–Шапиро. является

${\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 -автоматический.

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

Обе последовательности Баума – Свита ( OEIS : A086747 ) и обычная последовательность складывания бумаги. ( OEIS : A014577 ) являются автоматическими. Кроме того, общая последовательность складывания бумаги с периодической последовательностью складок также является автоматической.

Свойства

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

• Каждая автоматическая последовательность представляет собой морфическое слово .
• Для k ≥ 2 и r ≥ 1 последовательность является k -автоматической тогда и только тогда, когда она k ^р -автоматический. Этот результат принадлежит Эйленбергу.
• Для h и k мультипликативно независимых последовательность одновременно является h -автоматической и k -автоматической тогда и только тогда, когда она в конечном счете периодична. Этот результат принадлежит Кобэму, также известному как теорема Кобэма . с многомерным обобщением Семенова.
• Если u ( n ) — k -автоматическая последовательность над алфавитом Σ и f — равномерный морфизм из Σ ^∗ в другой алфавит ∆ ^∗ , то f ( u ) является k -автоматической последовательностью над ∆.
• Если u ( n ) — k -автоматическая последовательность, то последовательности u ( k ^н ) и u ( k ^н − 1) в конечном итоге являются периодическими. И наоборот, если u ( n ) является предельно периодической последовательностью, то последовательность v, определяемая v ( k ^н ) = u ( n ) и в противном случае ноль является k -автоматическим.

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

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

$t=011010011\dots$

быть словом Туэ-Морса. Позволять $s$ — слово, полученное путем объединения последовательных членов в последовательности длин серий. $t$. Затем $s$ начинается

$s=12112221\dots .$.

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

$h(1)=121,h(2)=12221.$

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

но не для $n=1864135$.

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

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

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

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

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

является $k$-автоматически тогда и только тогда, когда $\deg p\leq 1$ или $m\mid k-1$.

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

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

Обобщения

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

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

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

Логический подход

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

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

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

Программное обеспечение Walnut, разработанный Хамуном Мусави, реализует процедуру принятия решения для определения многих свойств определенных автоматических слов, таких как слово Туэ-Морса. Эта реализация является следствием вышеупомянутой работы над логическим подходом к автоматическим последовательностям.

См. также

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

Ссылки

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

Дальнейшее чтение

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