자동 시퀀스

수학과 이론 컴퓨터 과학에서, 자동 수열()은 유한 자동화로 특징지어지는 용어의 무한 수열이다.자동 시퀀스 a(n)의 n번째 항은 어떤 고정 기저 ^[1][2]k에서 n의 숫자를 받아들이는 유한 자동화에서 도달한 최종 상태의 매핑입니다.

자동 집합은 음이 아닌 정수 S의_S 집합으로, 특성 함수 χ의_S 값 순서가 자동 시퀀스입니다. 즉, χ_S(n)이 k-자동이면 S이고, n $∈$ {{$displaystyle \in}$ $S이면$ χ(n) = 1이고, 그렇지 않으면 ^[3][4]0입니다.

정의.

자동 시퀀스는 여러 가지 방법으로 정의할 수 있으며, 모두 동일합니다.네 가지 일반적인 정의는 다음과 같습니다.

오토마타 이론

양의 정수가 되고, D = (Q, Δ_k, Δ, q₀, Δ, Δ)가 출력을 갖는 결정론적 유한 자동자라고 하자.

• Q는 유한한 상태 집합입니다.
• 입력 알파벳 Δ는_k base-k 표기법에서 가능한 숫자 집합 {0,1,...,k-1}으로 구성됩니다.
• ◦ : Q × Δ_k → Q는 전이 함수입니다;
• q₀ ◦ Q는 초기 상태입니다.
• 출력 알파벳 Δ는 유한 집합입니다.
• τ : Q → δ는 내부 상태 집합에서 출력 알파벳으로의 출력 함수 매핑입니다.

숫자₁₂ ss...s로_t 구성된 문자열에 대한 δ의 작용을 다음과 같이 정의하여 전환 기능 δ을 한 자리에서 숫자 문자열에 대한 작용으로 확장합니다.

δ(q,s) = δ(δ(q,s₁₂...s_t-1), s_t).

다음과 같이 양의 정수 집합에서 출력 알파벳 Δ까지의 함수 a를 정의합니다.

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

여기서 s(n)는 기본 k로 작성됩니다.그런 다음 시퀀스 a = a(1)a(2)a(3)...k-자동 ^[1]시퀀스입니다.

가장 유의한 숫자로 시작하는 s(n)의 기본 자릿수를 읽는 자동 장치를 직독이라고 하며, 가장 유의하지 않은 숫자로 시작하는 자동 장치를 ^[4]역독이라고 합니다.위의 정의는 s(n)가 직접 ^[5]판독인지 역 판독인지를 유지합니다.

치환

자유 모노이드의$$$\sigma {\displaystyle {\mathrm{}}^{}}$ \ $displaystyle \ varphi$$\phi$$$ \ $displaystyle$ \ $Sigma$^{*}}를 automata-theory의 경우처럼$$τ \ $displaystyle$\ $tau$}를$$$$ 코딩($즉,$ $1{\displaystyle \mathrm{}}$ \ $displaystyle$ 1$}$ - uniformism)으로 합니다.$만약{\displaystyle }$w{$displaystyle$$$w$\}$가$$${\displaystyle \phi }$의 고정점이라면, 즉, w${\displaystyle }$${\displaystyle =}$${\displaystyle }$${\displaystyle \phi }$ ($)$ {$displaystyle$$$w=\$varphi (w$$라면{\displaystyle }$, s $=$ ($)$ {$displaystyle$ s$=\$$varphi$ ($w)}$는 k-자동 ^[6]시퀀스입니다.반대로, 모든 k-자동 시퀀스는 이러한 ^[4]방식으로 얻을 수 있습니다.이 결과는 코밤에 기인하며, 문헌에서 코밤의 작은 ^[2][7]정리로 언급됩니다.

k개의

2파운드.시퀀스(n)의 k-커널은 다음과 같은 순서의 집합입니다.

${\displaystyle K_{k}=\{s(k^{e}n+r):e\geq 0(으)로 변환된 텍스트{ 및 }}0\leq r\leq k^{e}-1\}.$

대부분의 경우 시퀀스의 k-커널은 무한합니다.그러나 k-커널이 유한하면 시퀀스(n)는 k-자동이고, 그 반대도 마찬가지입니다.이것은 ^[8][9][10]아일렌베르크 때문입니다.

따라서 k-자동 시퀀스는 반드시 유한 알파벳의 시퀀스입니다.

형식 멱급수

u(n)가 알파벳 Ω 위의 시퀀스라고 가정하고 Ω에서 유한 필드 F로_q 가는 주입 함수 β가 있다고 가정합니다. 여기서 일부 소수 p에 대한 q = p입니다ⁿ.관련된 공식 멱급수는 다음과 같습니다.

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

그러면 이 공식 멱급수가 F(X)에 대해_q 대수적인 경우에만 수열 u가 q-자동이 됩니다.이 결과는 Christol에 의한 것이며, 문헌에서 Christol의 ^[11]정리로 언급됩니다.

역사

자동 시퀀스는 1960년에 ^[12]부치에 의해 도입되었지만, 그의 논문은 문제에 대해 논리적 이론적 접근을 취했고 이 기사에서 발견된 용어를 사용하지 않았습니다.자동 시퀀스의 개념은 1972년 코밤에 의해 더 연구되었고, 그는 이 시퀀스를 "균일 태그 시퀀스"^[7]라고 불렀습니다.

"자동 시퀀스"라는 용어는 데스하우어의 ^[13]논문에 처음 등장했습니다.

예

다음 시퀀스는 자동입니다.

투에-모스 수열

투에-모스 수열 t(n)(OEIS: A010060)는 형태론 0 → 01, 1 → 10의 고정점입니다.투에-모스 수열의 n번째 항은 n의 기저-2 표현에서 1 모듈로 2의 수를 세기 때문에, 여기에 그림과 같은 출력을 가진 2 상태 결정론적 유한 자동화에 의해 생성됩니다.여기서 상태₀ q는 n의 표현에 짝수 개의 숫자가 있음을 나타내고 상태₁ q는 홀수 개의 숫자가 있음을 나타냅니다.따라서, 화-모스 수열은 2-자동입니다.

주기-이중수열

주기 배가 시퀀스 d(n)의 n번째 항(OEIS: A096268)은 2 나누기 n의 최고 거듭제곱 지수의 패리티로 결정됩니다.또한 모피즘 0 → 01, 1 → ^[14]00의 고정점이기도 합니다.초기 항 w = 0으로 시작하여 w에서 2-균일한 형태론을 반복하는데, 여기서 φ(0) = 01과 φ(1) = 00은 주기-균일한 순서가 φ(w)의 고정점이므로 2-자동임이 분명합니다.

루딘-샤피로 수열

루딘-샤피로 수열(n)의 n번째 항(OEIS: A020985)은 n의 기저-2 표현에서 연속된 항의 수에 의해 결정됩니다.루딘-샤피로^[15] 수열의 2개의 커널은 다음과 같습니다.

$표시(\style{aligned}r(2n)&=r(n),\r(4n+1)&=r(n),\r(8n+7)&=r(2n+1),\r(16n+3)&=r(4n+3).\end{aligned}}}$

2-커널은 r(n), r(2n+1), r(4n+3), r(8n+3)로만 구성되므로 유한하므로 루딘-샤피로 수열은 2-자동입니다.

기타 시퀀스

Baum-Sweet^[16] 시퀀스(OEIS: A086747)와 일반 종이 접기^[17][18][19] 시퀀스(OEIS: A014577)는 모두 자동입니다.또한 주기적인 접힘 순서가 있는 일반적인 용지 접힘 순서도 ^[20]자동입니다.

특성.

자동 시퀀스는 여러 가지 흥미로운 속성을 나타냅니다.이러한 속성의 완전하지 않은 목록은 아래에 나와 있습니다.

• 모든 자동 시퀀스는 형태적인 ^[21]단어입니다.
• k ≥ 2 및 r ≥ 1의 경우 시퀀스가 k-자동인^r 경우에만 k-자동입니다.이 결과는 아일렌베르크 ^[22]때문입니다.
• h와 k가 곱셈적으로 독립적인 경우, 시퀀스는 h-자동과 k-자동 둘 다입니다.^[23]이 결과는 코브햄의 ^[24]정리라고도 알려진 코브햄의 정리에 ^[25][26]기인하며, 세메노프로 인한 다차원 일반화에 기인합니다.
• 만약 u(n)가 알파벳 Ω에 대한 k-자동 수열이고 f가^∗ Ω에서 다른 알파벳^∗ Ω에 대한 균일한 형태라면, f(u)는 ^[27]Ω에 대한 k-자동 수열입니다.
• 만약 u(n)가 k-자동 시퀀스라면, 시퀀스 u(kⁿ)와 u(kⁿ - 1)는 ^[28]결국 주기적입니다.반대로, 만약 u(n)가 궁극적으로 주기적인 수열이라면, v(kⁿ) = u(n)로 정의된 수열 v는 ^[29]k-자동입니다.

자동성 입증 및 반증

후보 $시퀀스{\displaystyle }$ $=$ (${\displaystyle s_{}{}_n}$ ) n ${\displaystyle {\ge }_{}}$ {{$displaystyle$ s=($s_{n})_{n\geq$0$\}\}$이 주어지면, 일반적으로 자동성을 증명하는 것보다 더 쉽습니다.k-자동 시퀀스의 커널 특성화를 통해 $k-커널{\displaystyle {}_{}}$ $(s)$에서 무한히 많은 고유한 요소를 생성하여$$s$\displaystyle$$$K_$$$${k}가 k-자동이 $아님$을 보여주기에 충분합니다.경험적으로 커널의 항 일치를 확인하여 자동성을 증명하려고 할 수 있지만, 이는 때때로 잘못된 추측으로 이어질 수 있습니다.예를 들면,

${\displaystyle t=011010011\delay}$

화-모스 단어입니다.$displaystyle은$ t의 $런{\displaystyle }$ 길이$$순서로 연속된 항을 연결하여 부여한 $단어$입니다$.$$그러면{\displaystyle }${\$displaystyle}$이(가) 시작됩니다.

${\displaystyle s}$ $=$ $…({displaystyle$ s= $12112221\discovery$

s$\displaystyles$는 형태론의 $고정점{\displaystyle {}^{}}$ h${\displaystyle {}^{}{\omega }^{}}$ ($)$ {\$displaystyle$$$h$^{\omega }(1)$인 것으로 $알려져{\displaystyle }$ 있습니다.

$디스플레이 스타일 h(1)=121,h(2)=12221.$

$단어{\displaystyle }${\$displaystyles}$는 2-자동은 아니지만, 2-커널의 특정 요소는 많은 용어에 일치합니다.예를 들어, 0${\displaystyle }$≤ ${\displaystyle n}$≤ $1864134$의 ${\displaystyle 경우\mathrm{}}$ $s{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{16}}_{}}$n + $=$ s ${\displaystyle {\mathrm{64}}_{}}$n + ${\displaystyle \text{1}}$입니다$({16 n+1$}=$s_{64$ n$+1}{\text{ for }}0\leq$ n$\leq 1864134}).$

그러나 n $=$ $({displaystyle$ n= $1864135$^[30]에는 해당되지 않습니다.

자동으로 추측되는 시퀀스를 고려할 때, 실제로 그것이 실제로 존재한다는 것을 증명하기 위한 몇 가지 유용한 접근법이 있습니다.한 가지 접근법은 시퀀스를 제공하는 출력으로 결정론적 자동화를 직접 구성하는 것입니다.알파벳 ${displaystyle \Delta$로 작성된 ($)$ ${\displaystyle n_{}}$≥$$ {{$n}$$_{n$$\geq$ 0$}$을(를) 입력하고$,$ ($)$ k {\$displaystyle$$k$$}$가 n$${\$displaystyle$n}의 ${\displaystyle }$k 확장을 나타내도록 합니다$.{\displaystyle }$$그런{\displaystyle }$ 다음 시퀀스$=$ (${\displaystyle s_{}{}_{}{}_{}}$n ) $≥$ 0 {{$displaystyle$ s$=(s_{n})_{n\geq$ 0$$$}}$은$$k\$displaystyle$ k$($각각의$$ 섬유인 경우에만 자동)입니다.

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

는 정규 ^[31]언어입니다.섬유의 규칙성을 확인하는 것은 종종 정규 언어에 대한 펌핑 보조 장치를 사용하여 수행될 수 있습니다.

만약 sk (n) {{displaystyle s_{k}(n)}가 n{displaystyle n}과 p(X)의 기저 k(displaystyle k) 확장에 있는 자릿수의 합을 의미한다면, k ≥ 2 {\displaystyle k\geq 2}, m ≥ 1 {\displaystyle m\geq 1}이 정수인 다항식이다

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

${\displaystyle \mathrm{k}}$$(\displaystyle$ k$}$ - ≤ $(\displaystyle \displaystyle$ \displaystyle $p\leq$1) $또는$ m${\displaystyle k}$-$$({$displaystyle$ m$\mid k-1$^[32]인 경우에만$$ 자동입니다.

1-자동 시퀀스

k-자동 시퀀스는 일반적으로 k ≥ ^[1]2에 대해서만 정의됩니다.1-자동 시퀀스를 n번째 항이 n에 대한 단항 표기법, 즉 (1)ⁿ에 의존하는 시퀀스로 정의하여 k = 1까지 개념을 확장할 수 있습니다.유한 상태 자동화는 결국 이전에 방문한 상태로 돌아가야 하기 때문에, 모든 1-자동 시퀀스는 궁극적으로 주기적입니다.

일반화

자동 시퀀스는 정의 또는 입력 시퀀스의 변화에 대해 견고합니다.예를 들어, 자동 이론적 정의에서 언급한 것처럼, 주어진 시퀀스는 입력 시퀀스의 직접 및 역방향 판독 모두에서 자동으로 유지됩니다.또한 대체 숫자 집합이 사용되거나 기본값이 음수일 때, 즉 입력 시퀀스가 ^[33]기본 k가 아닌 기본 k로 표시될 때 시퀀스는 자동으로 유지됩니다.그러나 대체 숫자 집합을 사용하는 것과 달리 기본값을 변경하면 시퀀스의 자동성에 영향을 줄 수 있습니다.

자동 시퀀스의 영역은 양면 자동 시퀀스를 통해 자연수에서 정수로 확장될 수 있습니다.이것은 k가 주어졌을 때, 모든 정수가${\displaystyle \underset{}{}}$${\displaystyle {}_{}}$ ${\displaystyle \underset{}{0}}$≤ ${\displaystyle \underset{}{i}\underset{}{\le }{}_{}{rai}_{}}$ (${\displaystyle {}^{}}$-${\displaystyle {}^{}{k}^{}}$ ) i$,$ \ $displaystyle$ \$sum _$ {$0\leqi\leq$ r$}$$a_{$${\displaystyle i}$$}(-k)^{$i$$}의 형태로 고유하게 표현될 수 있다는 사실에서 비롯됩니다. ${\displaystyle {여기}_{}}$서 i $,$ ${\displaystyle \dots ,}$ k - ${\displaystyle 1}$ ${i} {\dots$, $k-1$그런 다음, 양변 무한 시퀀스 a(n)_{n ${\displaystyle \in \mathbb {Z} }$}는 연속 a(n)_{n ≥ 0}와 a(-n)_{n ≥ 0}가 ^[34]k-자동인 경우에만 (-k)-자동입니다.

k-자동 시퀀스의 알파벳은 k-정규 ^[35]시퀀스를 통해 유한 크기에서 무한 크기로 확장할 수 있습니다.k-정규 시퀀스는 k-커널이 유한하게 생성되는 시퀀스로 특징지을 수 있습니다.모든 경계 k-정규 시퀀스는 ^[36]자동입니다.

논리적 접근

많은 2-자동 $시퀀스{\displaystyle }$ $=$ (${\displaystyle s_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle \ge }$$$ {\$displaystyle$ s = ($s_{n)_{n\geq$0$\}\}$에 대해, 맵 n s$$ \$displaystyle$ n$\mapstos_{n}$은 1차 ${\displaystyle \text{이론}}$ FO ${\displaystyle (N\mathbb{},}$ ${\displaystyle +,}$ ${\displaystyle 0,}$ ${\displaystyle 1,}$ ${\displaystyle {}_{}}$)$${style ${\text}$를 $표시$하는 특성을 가지고 있습니다.$FO}}(\mathbb {N},+0,1,n\mapstos_{n}})$을(를) 결정할 수 있습니다.자동 시퀀스의 많은 사소한 속성이 1차 논리로 작성될 수 있기 때문에 결정 절차를 실행하면 ^[37]이러한 속성을 기계적으로 증명할 수 있습니다.

예를 들어, Thue-Morse 단어의 다음 특성은 모두 이러한 방식으로 기계적으로 확인할 수 있습니다.

• Thue-Morse 단어는 겹치지 않습니다. 즉, ${displaystyle cxc}$ $형식$의 단어를 포함하지 않습니다. $여기$서 c${displaystyle$ c$}$는 단일 $문자$이고 w${displaystyle$ w$}$는 빈 단어일 수 있습니다.
• 비어 있지 않은 $단어{\displaystyle }$ w${displaystyle$ w$}$와 x $=$ ${\displaystyle \mathrm{wy}}${{$displaystyle$ x=$displaystyle$w$\}$이(가) 있을 경우 비어 있지 않은 $단어{\displaystyle }$ $x{\displaystyle }$${$$displaystyle$$$x}에 경계가 표시됩니다.Thue-Morse 단어에는 ^[38]1보다 큰 각 길이에 대한 경계 요인이 포함되어 있습니다.
• (${\displaystyle n{}_{}}$ ${\displaystyle {2\mathrm{}}_{}{\notin }^{}1}$ (${\displaystyle {01}^{}}$ ∗${\displaystyle {}^{}{}^{}\mathrm{}}$ ) ${\displaystyle {\ast }^{}}$ $∗ 1 {{2}\notin$1 ($01^{*}0)^{*}10$$^{*}$$1$$$$}$인 경우에만 ${\displaystyle {투에-모스\mathrm{}}_{}}$ $단어$에 길이 $n{\displaystyle }${{$displaystyle$$$n}의$$ 비경계 인자가 있습니다$.{\displaystyle }$ 여기서 ($n)$2${\$$displaystyle$ n$\}$^[39]의 이진 표현을 $나타냅니다{\displaystyle }$.

하문 무사비가 개발한 ^[40][41]월넛 소프트웨어는 특정 자동 단어의 많은 속성을 결정하기 위한 결정 절차를 구현합니다.이 구현은 자동 시퀀스에 대한 논리적 접근 방식에 대한 위의 작업의 결과입니다.

참고 항목

• 뷔치 산술

메모들

레퍼런스

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
• Cobham, Alan (1972). "Uniform tag sequences". Mathematical Systems Theory. 6 (1–2): 164–192. doi:10.1007/BF01706087. S2CID 28356747.
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 978-0-521-84802-2. Zbl 1133.68067.
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 978-3-540-44141-0. Zbl 1014.11015.

진일보한 내용

• Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006.
• Loxton, J. H. (1988). "13. Automata and transcendence". In Baker, A. (ed.). New Advances in Transcendence Theory. Cambridge University Press. pp. 215–228. ISBN 978-0-521-33545-4. Zbl 0656.10032.
• Rowland, Eric (2015). "What is ... an automatic sequence?". Notices of the American Mathematical Society. 62 (3): 274–276. doi:10.1090/noti1218.
• Shallit, Jeffrey (1999). "Number theory and formal languages". In Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M. (eds.). Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996. The IMA volumes in mathematics and its applications. Vol. 109. Springer-Verlag. pp. 547–570. ISBN 978-0-387-98824-5.