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

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

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

Определение

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

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

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

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

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

δ (q,s) = δ (δ (q₀, s₁s₂...s_т-1), s_т).

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

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

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

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

Замена

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

k-ядро

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

${displaystyle K_{k}(s)={s(k^{e}n+r):egeq 0{ ext{ and }}0leq rleq k^{e}-1}.}$

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

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

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

Позволять ты(п) - последовательность над алфавитом Σ, и предположим, что существует инъективная функция β от Σ к конечное поле F_q, где q = п^п для некоторых премьер п. Связанный формальный степенной ряд является

${displaystyle sum _{igeq 0}eta (u(i))X^{i}.}$

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

История

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle t=011010011dots }$

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

${displaystyle s=12112221dots .}$.

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

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

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

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

Если предположить, что последовательность автоматическая, есть несколько полезных подходов для ее доказательства. Один из подходов состоит в том, чтобы напрямую построить детерминированный автомат с выходом, который дает последовательность. Позволять ${displaystyle (s_{n})_{ngeq 0}}$ написано в алфавите ${displaystyle Delta }$, и разреши ${displaystyle (n)_{k}}$ обозначают основание-${displaystyle k}$ расширение ${displaystyle n}$. Тогда последовательность ${displaystyle s=(s_{n})_{ngeq 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 kgeq 2}$, ${displaystyle mgeq 1}$ являются целыми числами, то последовательность

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

является ${displaystyle k}$-автоматически тогда и только тогда, когда ${displaystyle deg pleq 1}$ или ${displaystyle mmid k-1}$.^[32]

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

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

Обобщения

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

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

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

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

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

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

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

Программное обеспечение Walnut,^[40][41] разработанный Hamoon Mousavi, реализует процедуру принятия решения для определения многих свойств определенных автоматических слов, таких как слово Thue – Morse. Эта реализация является следствием вышеупомянутой работы над логическим подходом к автоматическим последовательностям.

Смотрите также

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

Примечания

1. Allouche & Shallit (2003) стр. 152
2. Berstel et al (2009) стр. 78
3. Allouche & Shallit (2003) стр. 168
4. Пифей Фогг (2002) стр. 13
5. Пифей Фогг (2002) стр. 15
6. Allouche & Shallit (2003) стр. 175
7. Кобэм (1972)
8. Allouche & Shallit (2003) стр. 185
9. Lothaire (2005) стр. 527
10. Berstel & Reutenauer (2011) стр. 91
11. Кристол, Г. (1979). "Престижные периодические ансамбли k-разведка ". Теорет. Comput. Наука. 9: 141–145. Дои:10.1016/0304-3975(79)90011-2.
12. Бючи, Дж. Р. (1960). Слабая арифметика второго порядка и конечные автоматы. Z. Math. Логик Grundlagen Math. 6. С. 66–92. Дои:10.1007/978-1-4613-8928-6_22. ISBN  978-1-4613-8930-9.
13. Deshouillers, J.-M. (1979–1980). "La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini". Séminaire de Théorie des Nombres de Bordeaux: 5.01–5.22.
14. Allouche & Shallit (2003) стр. 176
15. Allouche & Shallit (2003) стр. 186
16. Allouche & Shallit (2003) стр. 156
17. Berstel & Reutenauer (2011) стр. 92
18. Allouche & Shallit (2003) стр. 155
19. Lothaire (2005) стр. 526
20. Allouche & Shallit (2003) стр. 183
21. Lothaire (2005) стр. 524
22. Эйленберг, Сэмюэл (1974). Автоматы, языки и машины. А. Орландо: Академическая пресса. ISBN  978-0-122-34001-7.
23. Allouche & Shallit (2003), стр. 345–350.
24. Кобхэм, А. (1969). «О базисной зависимости множеств чисел, распознаваемых конечными автоматами». Математика. Теория систем. 3 (2): 186–192. Дои:10.1007 / BF01746527.
25. Семенов, А. Л. (1977). «Пресбургерность регулярных предикатов в двух системах счисления». Сибирск. Мат. Ж. (на русском). 18: 403–418.
26. Point, F .; Брюер, В. (1997). «О теореме Кобама-Семенова». Теория вычислительных систем. 30 (2): 197–220. Дои:10.1007 / BF02679449.
27. Lothaire (2005) стр. 532
28. Lothaire (2005) стр. 529
29. Berstel & Reutenauer (2011) стр. 103
30. Allouche, G .; Allouche, J.-P .; Шаллит, Дж. (2006). "Kolam indiens, dessins sur le sable aux îles Vanuatu, Courbe de Sierpinski et morphismes de monoïde". Annales de l'Institut Fourier. 56 (7): 2126. Дои:10.5802 / aif.2235.
31. Аллуш и Шаллит (2003) стр. 160
32. Аллуш и Шаллит (2003) стр. 197
33. Allouche & Shallit (2003) стр. 157
34. Allouche & Shallit (2003) стр. 162
35. Allouche, J.-P .; Шаллит, Дж. (1992), "Кольцо k-регулярные последовательности », Теорет. Comput. Sci., 98 (2): 163–197, Дои:10.1016 / 0304-3975 (92) 90001-в
36. Шаллит, Джеффри. «Логический подход к автоматическим последовательностям, часть 1: автоматические последовательности и k-Регулярные последовательности » (PDF). Получено 1 апреля, 2020.
37. Шаллит, Дж. «Логический подход к автоматическим последовательностям: часть 1» (PDF). Получено 1 апреля, 2020.
38. Шаллит, Дж. «Логический подход к автоматическим последовательностям: часть 3» (PDF). Получено 1 апреля, 2020.
39. Шаллит, Дж. «Логический подход к автоматическим последовательностям: часть 3» (PDF). Получено 1 апреля, 2020.
40. Шаллит, Дж. "Walnut Software". Получено 1 апреля, 2020.
41. Мусави, Х. (2016). "Автоматическое доказательство теорем в орехе". arXiv:1603.06017 [cs.FL ].

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

• Аллуш, Жан-Поль; Шаллит, Джеффри (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. Дои:10.1007 / BF01706087.
• Лотэр, М. (2005). Прикладная комбинаторика слов. Энциклопедия математики и ее приложений. 105. Коллективная работа Жана Берштеля, Доминика Перрена, Максима Крошмора, Эрика Ляпорта, Мериара Мори, Нади Пизанти, Мари-Франс Саго, Гезин Райнерт, Софи Шбат, Майкл Уотерман, Филипп Жаке, Войцех Шпанковски, Доминик Пулалхон, Жиль Шеффер, Роман Колпаков, Грегори Кушеров, Жан-Поль Аллуш и Валери Берте. Кембридж: Издательство Кембриджского университета. 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, Дои:10.1090 / noti1218.
• Шаллит, Джеффри (1999). «Теория чисел и формальные языки». В Хейхал, Деннис А.; Фридман, Джоэл; Гуцвиллер, Мартин К.; Одлызко, Андрей М. (ред.). Новые приложения теории чисел. По материалам летней программы IMA, Миннеаполис, Миннесота, США, 15–26 июля 1996 г.. Объемы IMA по математике и ее приложениям. 109. Springer-Verlag. С. 547–570. ISBN  978-0-387-98824-5.