自動シーケンス

数学と理論計算機科学において、自動数列（k自動数列、またはk認識数列とも呼ばれ、使用される数字の基数がkであることを示す）は、有限オートマトンによって特徴付けられる項の無限数列である。自動数列のn番目の項a ( n ) は、ある固定された基数kにおける数nの桁を受け入れる有限オートマトンで到達する最終状態のマッピングである。^{[1] [2]} 

自動集合とは、その特性関数χ _Sの値の列が自動列となる非負整数Sの集合である。つまり、 χ _S ( n )がk自動であればS はk自動であり、n Sであれば χ _S ( n ) = 1 、それ以外は 0 である。^{[3] [4]} ${\displaystyle \in}$ 

自動シーケンスはさまざまな方法で定義できますが、その方法はすべて同等です。一般的な 4 つの定義は次のとおりです。

kを正の整数とし、D = ( Q , Σ _k , δ, q ₀ , Δ, τ)を出力を持つ決定性有限オートマトン とする。ここで、

• Q は状態の有限集合です。
• 入力アルファベットΣk_は、基数k表記の可能な数字の集合{0,1,..., k -1}から構成されます。
• δ : Q × Σ _k → Qは遷移関数である。
• q ₀ ∈ Qは初期状態です。
• 出力アルファベットΔは有限集合であり、
• τ: Q → Δ は、内部状態のセットから出力アルファベットへのマッピングの出力関数です。

遷移関数 δ を単一の数字に作用するものから数字の文字列に作用するものに拡張し、数字s ₁ s ₂ ... s _tからなる文字列sに対する δ の作用を次のように定義します。

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

次のように、正の整数の集合から出力アルファベット Δ への 関数aを定義します。

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

ここでs ( n )はk進数で書かれたnである。すると数列a = a (1) a (2) a (3)...はk自動数列となる。^[1]

s ( n )のk進数桁を最上位桁から読み取るオートマトンを直接読み取るオートマトンを指し、最下位桁から読み取るオートマトンを逆読みと呼びます。^[4]上記の定義は、s ( n )が直接読みの場合も逆読みの場合も当てはまります。^[5]

を自由モノイドのk一様射とし、をオートマトン理論的ケースのように符号化（つまり-一様射）とします。 がの不動点である場合、つまり である場合、 はk -自動列です。^[6]逆に、すべてのk -自動列はこの方法で得られます。^{[4]この結果は}コブハムによるもので、文献ではコブハムの小定理と呼ばれています。^{[2] [7]}${\displaystyle \varphi}$ ${\displaystyle \Sigma^{*}}$${\displaystyle \tau}$${\displaystyle 1}$${\displaystyle w}$${\displaystyle \varphi}$${\displaystyle w=\varphi (w)}$${\displaystyle s=\tau (w)}$

k  ≥ 2とする。シーケンスs ( n )のkカーネルは、部分シーケンスの集合である。

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

ほとんどの場合、シーケンスのk核は無限です。しかし、 k核が有限の場合、シーケンスs（n）はk自動であり、逆もまた真です。これはアイレンバーグによるものです。^{[8] [9] [10]}

したがって、k自動シーケンスは必然的に有限アルファベット上のシーケンスになります。

u ( n ) をアルファベット Σ 上の列とし、 Σ から有限体 F q への単射関数 β が存在するとする。ここで、_ある素数pに対してq = p n^とする。関連する形式的冪級数は

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

すると、この形式的な冪級数がF _q ( X )上で代数的である場合に限り、数列uはq自動的となる。この結果はクリストルによるもので、文献ではクリストルの定理と呼ばれている。^[11]

自動シーケンスは1960年にビュッヒによって導入されましたが^[12] 、彼の論文ではより論理理論的なアプローチが取られており、この論文で使用されている用語は使用されていませんでした。自動シーケンスの概念は1972年にコブハムによってさらに研究され、彼はこれらのシーケンスを「ユニフォームタグシーケンス」と呼びました^{[7] 。}

「自動シーケンス」という用語は、デシュイエールの論文で初めて登場しました。^[13]

次のシーケンスは自動的に実行されます。

Thue –Morse 数列 t ( n ) ( OEIS : A010060 ) は、射 0 → 01, 1 → 10 の不動点です。Thue–Morse 数列のn番目の項は、 nの 2 進表現における 2を法とする1の数を数えるため、ここに示す出力を持つ 2 状態決定性有限オートマトンによって生成されます。ここで、状態q _0はnの表現に 1 が偶数個あることを示し、状態q ₁は1 が奇数個あることを示します。したがって、Thue–Morse 数列は 2 オートマトンです。

周期倍加列d ( n ) ( OEIS : A096268 ) のn番目の項は、 n を割り切る 2 の最大の累乗の指数の偶奇によって決まります。また、0 → 01, 1 → 00 の射の不動点でもあります。^[14]初期項w = 0 から始めて、 φ(0) = 01 および φ(1) = 00 であるw上の 2 一様射 φ を反復すると、周期倍加列が φ( w )の不動点であり、したがって 2 自動的であることがわかります。

ルディン・シャピロ数列r ( n )( OEIS :A020985 )のn番目の項は、 nの2進数表現における連続する1の数によって決定される。ルディン・シャピロ数列^[15]の2核は、

${\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 ( 2n  +1)、r (4n +  3)、r ( 8n  +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 ( k ⁿ ) = u ( n )で定義され、それ以外の場合は0であるシーケンスvはk自動です。^[29]

候補シーケンス が与えられた場合、その自動性を証明するよりも反証する方が通常は簡単です。k自動シーケンスのkカーネル特性により、 kカーネル内に無限に多くの異なる要素を生成するだけで、がk自動でないことが示されます。 経験的に、 kカーネル内の項の一致をチェックすることで自動性を証明しようとするかもしれませんが、これは時々間違った推測につながる可能性があります。 たとえば、 ${\displaystyle s=(s_{n})_{n\geq 0}}$${\displaystyle K_{k}(s)}$${\displaystyle s}$

${\displaystyle t=011010011\dots }$

をThue-Morse語とする。を の連続する項を連結して得られる語とする。すると、 ${\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{ }}0\leq n\leq 1864134 の場合}$

しかし、 には当てはまりません。^[30]${\displaystyle n=1864135}$

自動的であると推測されるシーケンスが与えられた場合、それが実際に自動的であることを証明するためのいくつかの有用なアプローチがあります。1つのアプローチは、シーケンスを与える出力を持つ決定性オートマトンを直接構築することです。アルファベットで書かれ、の基底展開を表すとします。すると、シーケンスが-自動的であるためには、各ファイバーが ${\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}$

k自動シーケンスは通常、k  ≥ 2 の場合にのみ定義されます。 ^[1]この概念は、1 自動シーケンスを、n番目の項がnの単項表記に依存するシーケンスとして定義することで、 k = 1 に拡張できます。つまり、(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カーネルが有限生成されるシーケンスとして特徴付けることができます。すべての制限付き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})}$

たとえば、Thue-Morse語の次の特性はすべて、この方法で機械的に検証できます。

• Thue-Morse 語は重複がありません。つまり、 という形式の語は含まれません。ここで は単一の文字であり、 は空の語である可能性があります。${\displaystyle cxcxc}$${\displaystyle c}$${\displaystyle w}$
• 空でない単語が境界付きであるとは、空でない単語と、おそらく空の単語が で存在する場合である。Thue-Morse 語には、1 より大きい長さごとに境界付き因子が含まれる。^[38]${\displaystyle x}$${\displaystyle w}$${\displaystyle y}$${\displaystyle x=wyw}$
• Thue-Morse語に境界のない長さの因子が存在するのは、が の2進表現を表す場合のみである。^[39]${\displaystyle n}$${\displaystyle (n)_{2}\notin 1(01^{*}0)^{*}10^{*}1}$${\displaystyle (n)_{2}}$${\displaystyle n}$

Hamoon Mousaviによって開発されたソフトウェアWalnut ^{[40] [41]}は、Thue-Morse語などの特定の自動単語の多くの特性を決定するための決定手順を実装しています。この実装は、自動シーケンスへの論理的アプローチに関する上記の研究の結果です。

• ビュッヒ算術

• アルーシュ、ジャン=ポール、シャリット、ジェフリー(2003)。自動シーケンス: 理論、アプリケーション、一般化。ケンブリッジ大学出版局。ISBN 978-0-521-82332-6.ZBL1086.11015  。​
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009)。単語の組合せ論。クリストッフェル語と単語の繰り返し。CRM モノグラフ シリーズ。第 27 巻。プロビデンス、ロードアイランド州:アメリカ数学協会。ISBN 978-0-8218-4480-9.ZBL1161.68043  。​
• Berstel, Jean; Reutenauer, Christophe (2011).非可換有理数級数とその応用. 数学とその応用百科事典. 第137巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-19022-0.ZBL1250.68007  。​
• コブハム、アラン( 1972 )。「均一タグシーケンス」。数学システム理論。6 (1–2): 164–192。doi :10.1007/BF01706087。S2CID 28356747  。
• ロテール、M. (2005)。単語に組み合わせ論を応用。数学とその応用の百科事典。 Vol. 105. ジャン・ベルステル、ドミニク・ペラン、マキシム・クロシュモア、エリック・ラポルト、メリヤル・モーリ、ナディア・ピサンティ、マリー＝フランス・サゴ、ジェシーヌ・ライナート、ソフィー・シュバス、マイケル・ウォーターマン、フィリップ・ジャケ、ヴォイチェフ・シュパンコウスキー、ドミニク・ポラロン、ジル・シェーファーによる共同作品。ロマン・コルパコフグレゴリー・クチェロフ、ジャン＝ポール・アルーシュ、ヴァレリー・ベルテ。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-84802-2.ZBL1133.68067  。​
• ピテアス・フォッグ、N. (2002)。力学、算術、組み合わせ論における置換。数学の講義ノート。 Vol. 1794年。編集者ベルテ、ヴァレリー；フェレンチ、セバスチャン。モーデュイ、クリスチャン。シーゲル、A. ベルリン: Springer-Verlag。ISBN 978-3-540-44141-0.ZBL1014.11015  .​

• Berthé, Valérie; Rigo, Michel 編 (2010)。組合せ論、オートマトン、数論。数学とその応用百科事典。第 135 巻。ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-51597-9.ZBL1197.68006  。​
• ロクストン、JH (1988)。「13. オートマトンと超越性」。ベイカー、A. (編) 『超越理論の新進歩』。ケンブリッジ大学出版局。215～228 ページ。ISBN 978-0-521-33545-4.ZBL0656.10032  。​
• ローランド、エリック(2015)。「自動シーケンスとは何か?」アメリカ数学会の通知。62 (3): 274–276。doi : 10.1090/noti1218。
• Shallit, Jeffrey (1999)。「数論と形式言語」。Hejhal , Dennis A.、Friedman, Joel、Gutzwiller, Martin C.、Odlyzko, Andrew M. (編)。数論の新たな応用。1996 年 7 月 15 ～ 26 日に米国ミネソタ州ミネアポリスで開催された IMA サマー プログラムの議事録に基づく。数学とその応用に関する IMA 巻。第 109 巻。Springer -Verlag。pp . 547 ～ 570。ISBN 978-0-387-98824-5。