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

редактировать

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

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

Содержание

1 Определение
- 1.1 Теоретико-автоматная
- 1.2 Замена
- 1.3 k-ядро
- 1.4 Формальный степенной ряд
2 История
3 Примеры
- 3.1 Последовательность Туэ – Морса
- 3.2 Последовательность удвоения периода
- 3.3 Последовательность Рудина – Шапиро
- 3.4 Другие последовательности
4 Свойства
5 Доказательство и опровержение автоматизма
6 1-автоматические последовательности
7 Обобщения
8 Логический подход
9 См. Также
10 Примечания
11 Ссылки
12 Дополнительная литература

Определение

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

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

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

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

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

δ (q, s) = δ (δ (q 0, s 1s2... s t-1), s t).

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

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

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

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

Подстановка

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

k-ядро

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

K k (s) = {s (ken + r): e ≥ 0 и 0 ≤ r ≤ ke - 1}. {\ displaystyle K_ {k} (s) = \ {s (k ^ {e} n + r): e \ geq 0 {\ text {and}} 0 \ leq r \ leq k ^ {e} -1 \ }.}

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

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

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

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

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

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

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

История

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

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

Примеры

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

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

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

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

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

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

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

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

r (2 n) = r (n), r (4 n + 1) = r (n), r (8 n + 7) = r (2 n + 1), г (16 п + 3) = г (8 п + 3), г (16 п + 11) = г (4 п + 3). {\ Displaystyle {\ begin {align} 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 {align}}}

{\ displaystyle {\ begin {выровнено} 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 {align}}}

Поскольку 2- ядро состоит только из r (n), r (2n + 1), r (4n + 3) и r (8n + 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 = (sn) n ≥ 0 {\ displaystyle s = (s_ {n}) _ {n \ geq 0}}$ ${\ displaystyle s = (s_ {n}) _ {n \ geq 0}}$ , обычно легче опровергнуть ее автоматичность, чем Докажите это. С помощью k-ядерной характеристики k-автоматических последовательностей достаточно создать бесконечное количество различных элементов в k-ядре $K k (s) {\ displaystyle K_ {k} (s)}$ ${\ displaystyle K_ {k} (s)}$ чтобы показать, что $s {\ displaystyle s}$ $s$ не является k-автоматическим. Эвристически можно попытаться доказать автоматичность, проверив согласование терминов в k-ядре, но иногда это может приводить к неверным предположениям. Например, пусть

t = 011010011… {\ displaystyle t = 011010011 \ dots}

{\ displaystyle t = 011010011 \ dots}

будет словом Thue – Morse. Пусть $s {\ displaystyle s}$ $s$ будет словом, полученным путем объединения последовательных членов в последовательности длин серий $t {\ displaystyle t}$ $t$ . Затем $s {\ displaystyle s}$ $s$ начинается

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

{\ displaystyle s = 12112221 \ dots.}

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

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

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

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

, но не для $n = 1864135 {\ displaystyle n = 1864135}$ ${\ displaystyle n = 1864135}$ .

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

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

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

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

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

(sk (p (n)) (mod m)) n ≥ 0 {\ displaystyle (s_ {k} (p (n))) {\ pmod { m}}) _ {n \ geq 0}}

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

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

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

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

Обобщения

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

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

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

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

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

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

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

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

См. Также

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

Примечания

Ссылки

Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. ISBN 978-0-521-82332-6. Zbl 1086.11015.
Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и их повторения в словах. Серия монографий CRM. 27 . Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями. Энциклопедия математики и ее приложений. 137 . Кембридж: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
Кобэм, Алан (1972). «Единые последовательности тегов». Математика. Теория систем. 6 (1–2): 164–192. doi : 10.1007 / BF01706087.
Lothaire, M. (2005). Прикладная комбинаторика слов. Энциклопедия математики и ее приложений. 105 . Коллективная работа Жана Берштеля, Доминика Перрена, Максима Крошмора, Эрика Ляпорта, Мериара Мори, Нади Пизанти, Мари-Франс Саго, Жезин Рейнер, Софи Шбат, Майкла Уотермана, Филиппа Жаке, Войцех Шпанковски, Доминик Пулалхон, Жиль Шеффер, Роман Колпаков, Грегори Кушеров, Жан-Поль Аллуш и Валери Берте. Кембридж: Cambridge University Press. 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 . Кембридж: Cambridge University Press. 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). «Теория чисел и формальные языки». В Хейхал, Деннис А. ; Фридман, Джоэл; Гуцвиллер, Мартин К. ; Одлызко, Эндрю М. (ред.). Новые приложения теории чисел. На основе материалов летней программы IMA, Миннеаполис, Миннесота, США, 15–26 июля 1996 г. Тома IMA по математике и ее приложениям. 109 . Спрингер-Верлаг. С. 547–570. ISBN 978-0-387-98824-5.