Automatic sequence: Difference between revisions
Taylorsmith2 (talk | contribs) Undid revision 775641481 by Materialscientist (talk) - see previous edit summaries and talk page for details on my changes |
Taylorsmith2 (talk | contribs) Added history section, moved uncited references to further reading section |
||
Line 1: | Line 1: | ||
In [[mathematics]] and [[theoretical computer science]], an '''automatic sequence''' (also called a '''''k''-automatic sequence''' when one wants to indicate that the base of the numerals used is ''k'') is an infinite [[sequence]] of terms characterized by a [[finite automaton]]. The ''n''-th term of an automatic sequence ''a''(''n'') is a mapping of the final state reached in a finite automaton accepting the digits of the number ''n'' in some fixed [[radix|base]] ''k''.<ref name=as1>Allouche & Shallit (2003) p. 152</ref><ref name=BLRS78>Berstel et al (2009) p. 78</ref> |
In [[mathematics]] and [[theoretical computer science]], an '''automatic sequence''' (also called a '''''k''-automatic sequence''' or a '''''k''-recognizable sequence''' when one wants to indicate that the base of the numerals used is ''k'') is an infinite [[sequence]] of terms characterized by a [[finite automaton]]. The ''n''-th term of an automatic sequence ''a''(''n'') is a mapping of the final state reached in a finite automaton accepting the digits of the number ''n'' in some fixed [[radix|base]] ''k''.<ref name=as1>Allouche & Shallit (2003) p. 152</ref><ref name=BLRS78>Berstel et al (2009) p. 78</ref> |
||
An '''automatic set''' is a set of non-negative integers ''S'' for which the sequence of values of its characteristic function χ<sub>''S''</sub> is an automatic sequence; that is, ''S'' is ''k''-automatic if χ<sub>''S''</sub> is ''k''-automatic, where χ<sub>''S''</sub> = 1 if ''n'' <math>\in</math> ''S'' and 0 otherwise.<ref>Allouche & Shallit (2003) p. 168</ref><ref name=PF13/> |
An '''automatic set''' is a set of non-negative integers ''S'' for which the sequence of values of its characteristic function χ<sub>''S''</sub> is an automatic sequence; that is, ''S'' is ''k''-automatic if χ<sub>''S''</sub> is ''k''-automatic, where χ<sub>''S''</sub> = 1 if ''n'' <math>\in</math> ''S'' and 0 otherwise.<ref>Allouche & Shallit (2003) p. 168</ref><ref name=PF13/> |
||
Line 40: | Line 40: | ||
===Decimation=== |
===Decimation=== |
||
Let ''k'' <math>\geq</math> 2. For a sequence ''w'', we define the ''k-decimations'' of ''w'' for ''r'' = 0,1,...,''k'' − 1 to be the subsequences consisting of the letters in positions congruent to ''r'' modulo ''k''. The decimation kernel of ''w'' consists of the set of words obtained by all possible repeated decimations of ''w''. A sequence is ''k''-automatic if and only if the ''k''-decimation kernel is finite.<ref name=AS185>Allouche & Shallit (2003) p. 185</ref><ref name=ApCOw527>Lothaire (2005) p. 527</ref><ref name=BR91>Berstel & Reutenauer (2011) p. 91</ref> |
Let ''k'' <math>\geq</math> 2. For a sequence ''w'', we define the ''k-decimations'' of ''w'' for ''r'' = 0,1,...,''k'' − 1 to be the subsequences consisting of the letters in positions congruent to ''r'' modulo ''k''. The decimation kernel of ''w'' consists of the set of words obtained by all possible repeated decimations of ''w''. A sequence is ''k''-automatic if and only if the ''k''-decimation kernel is finite.<ref name=AS185>Allouche & Shallit (2003) p. 185</ref><ref name=ApCOw527>Lothaire (2005) p. 527</ref><ref name=BR91>Berstel & Reutenauer (2011) p. 91</ref> |
||
==History== |
|||
Automatic sequences were introduced by [[Julius Richard Büchi|Büchi]] in 1960,<ref>{{cite journal | first=Julius Richard | last=Büchi | title=Weak second-order arithmetic and finite automata | journal=Z. Math. Logik Grundlagen Math. | volume=6 | year=1960 | pages=66–92 | doi=10.1007/978-1-4613-8928-6_22 }}</ref> although his paper took a more logico-theoretic approach to the matter and did not use the terminology found in this article. The notion of automatic sequences was further studied by Cobham in 1972, who called these sequences "uniform [[Tag system|tag sequences]]".<ref>{{cite journal | first=Alan | last=Cobham | title=Uniform tag sequences | journal=Math. Systems Theory | volume=6 | year=1972 | pages=164–192 | doi=10.1007/BF01706087 }}</ref> The term "automatic sequence" first appeared in a paper of Deshouillers.<ref>{{cite journal | first=J.-M. | last=Deshouillers | title=La répartition modulo 1 des puissances de rationnels dans l’anneau des séries formelles sur un corps fini | journal=Séminaire de Théorie des Nombres de Bordeaux | year=1979–1980 | pages=5.01–5.22 }}</ref> |
|||
==Examples== |
==Examples== |
||
Line 82: | Line 85: | ||
* {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | url=http://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }} |
* {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | url=http://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }} |
||
* {{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }} |
* {{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }} |
||
⚫ | * {{cite book | editor1-last=Berthé | editor1-first=Valérie | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | isbn=978-0-521-51597-9 | zbl=1197.68006 }} |
||
*{{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Applied combinatorics on words | others=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é| series=Encyclopedia of Mathematics and Its Applications | volume=105 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2005 | isbn=0-521-84802-4 | zbl=1133.68067 }} |
*{{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Applied combinatorics on words | others=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é| series=Encyclopedia of Mathematics and Its Applications | volume=105 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2005 | isbn=0-521-84802-4 | zbl=1133.68067 }} |
||
⚫ | *{{cite book | first=J. H. | last=Loxton | chapter=13. Automata and transcendence | pages=215–228 | title=New Advances in Transcendence Theory | editor1-link=Alan Baker (mathematician) | editor1-first=A. | editor1-last=Baker | publisher=[[Cambridge University Press]] | year=1988 | isbn=0-521-33545-0 | zbl=0656.10032 }} |
||
* {{cite book | last=Pytheas Fogg | first=N. | others=Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=[[Springer-Verlag]] | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }} |
* {{cite book | last=Pytheas Fogg | first=N. | others=Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=[[Springer-Verlag]] | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }} |
||
==Further reading== |
|||
⚫ | * {{cite book | editor1-last=Berthé | editor1-first=Valérie | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | isbn=978-0-521-51597-9 | zbl=1197.68006 }} |
||
⚫ | *{{cite book | first=J. H. | last=Loxton | chapter=13. Automata and transcendence | pages=215–228 | title=New Advances in Transcendence Theory | editor1-link=Alan Baker (mathematician) | editor1-first=A. | editor1-last=Baker | publisher=[[Cambridge University Press]] | year=1988 | isbn=0-521-33545-0 | zbl=0656.10032 }} |
||
*{{citation | last = Rowland | first = Eric | title = What is ... an automatic sequence? | journal = Notices of the American Mathematical Society | volume = 62 | year = 2015 | pages = 274–276 | url = http://dx.doi.org/10.1090/noti1218}}. |
*{{citation | last = Rowland | first = Eric | title = What is ... an automatic sequence? | journal = Notices of the American Mathematical Society | volume = 62 | year = 2015 | pages = 274–276 | url = http://dx.doi.org/10.1090/noti1218}}. |
||
*{{cite book | editor1-first=Dennis A. | editor1-last=Hejhal | editor1-link=Dennis Hejhal | editor2-last=Friedman | editor2-first=Joel | editor3-last=Gutzwiller | editor3-first=Martin C. | editor3-link=Martin Gutzwiller | editor4-last=Odlyzko | editor4-first=Andrew M. | editor4-link=Andrew Odlyzko | title=Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996 | series=The IMA volumes in mathematics and its applications | volume=109 | publisher=[[Springer-Verlag]] | year=1999 | isbn=0-387-98824-6 | last=Shallit | first=Jeffrey | author1-link=Jeffrey Shallit | chapter=Number theory and formal languages | pages=547–570 }} |
*{{cite book | editor1-first=Dennis A. | editor1-last=Hejhal | editor1-link=Dennis Hejhal | editor2-last=Friedman | editor2-first=Joel | editor3-last=Gutzwiller | editor3-first=Martin C. | editor3-link=Martin Gutzwiller | editor4-last=Odlyzko | editor4-first=Andrew M. | editor4-link=Andrew Odlyzko | title=Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996 | series=The IMA volumes in mathematics and its applications | volume=109 | publisher=[[Springer-Verlag]] | year=1999 | isbn=0-387-98824-6 | last=Shallit | first=Jeffrey | author1-link=Jeffrey Shallit | chapter=Number theory and formal languages | pages=547–570 }} |
Revision as of 06:05, 16 April 2017
In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k.[1][2]
An automatic set is a set of non-negative integers S for which the sequence of values of its characteristic function χS is an automatic sequence; that is, S is k-automatic if χS is k-automatic, where χS = 1 if n S and 0 otherwise.[3][4]
Definition
Automatic sequences may be defined in a number of ways, all of which are equivalent. Four common definitions are as follows.
Automata-theoretic
Let k be a positive integer, and let D = (Q, Σk, δ, q0, Δ, τ) be a deterministic finite automaton with output, where
- Q is the finite set of states;
- the input alphabet Σk consists of the set {0,1,...,k-1} of possible digits in base-k notation;
- δ : Q × Σk → Q is the transition function;
- q0 ∈ Q is the initial state;
- the output alphabet Δ is similar to Σk; and
- τ : Σk → Δ is the output function mapping from the input alphabet to the output alphabet.
Extend the transition function δ from acting on single digits to acting on strings of digits by defining the action of δ on a string s consisting of digits s1s2...st as:
- δ(q,s) = δ(δ(q0, s1s2...st-1), st).
Define a function a from the set of positive integers to the output alphabet Δ as follows:
- a(n) = τ(δ(q0,s(n))),
where s(n) is n written in base k. Then the sequence a = a(1)a(2)a(3)... is a k-automatic sequence.[1]
An automaton reading the base k digits of s(n) starting with the most significant digit is said to be direct reading, while an automaton starting with the least significant digit is reverse reading.[4] The above definition holds whether s(n) is direct or reverse reading.[5]
Substitution
Let σ be a k-uniform morphism of the free monoid E∗, so that σ(E) Ek and which is prolongable[6] on e E; that is, σ(e) begins with e. Let A and π be defined as above. If w is a fixed point of σ—that is to say, w = σ(w)—then m = π(w) is a k-automatic sequence over A;[7] this is Cobham's theorem.[2] Conversely, every k-automatic sequence is obtained in this way.[4]
k-kernel
Let k 2. The k-kernel of the sequence s(n){n 0} is the set of sequences
A sequence s(n){n 0} is k-automatic if its k-kernel is finite.
It follows that a k-automatic sequence is necessarily a sequence on a finite alphabet.
Decimation
Let k 2. For a sequence w, we define the k-decimations of w for r = 0,1,...,k − 1 to be the subsequences consisting of the letters in positions congruent to r modulo k. The decimation kernel of w consists of the set of words obtained by all possible repeated decimations of w. A sequence is k-automatic if and only if the k-decimation kernel is finite.[8][9][10]
History
Automatic sequences were introduced by Büchi in 1960,[11] although his paper took a more logico-theoretic approach to the matter and did not use the terminology found in this article. The notion of automatic sequences was further studied by Cobham in 1972, who called these sequences "uniform tag sequences".[12] The term "automatic sequence" first appeared in a paper of Deshouillers.[13]
Examples
The following sequences are automatic:
- The Thue–Morse sequence is the fixed point of the morphism 0 → 01, 1 → 10. The 2-kernel consists of the sequence itself and its complement.[14] Hence the Thue–Morse sequence is 2-automatic. The n-th term is the parity of the sum of digits in the base-2 representation of n.[1][2][15][16] The associated power series T(z) satisfies
- over the field F2(z).[17]
- Rudin–Shapiro sequence[15][18]
- Baum–Sweet sequence[19]
- Regular paperfolding sequence[16][20][21] and a general paperfolding sequence with a periodic sequence of folds[22]
- The period-doubling sequence, defined by the parity of the power of 2 dividing n; also the fixed point of the morphism 0 → 01, 1 → 00.[23]
Properties
For given k and r, a set is k-automatic if and only if it is kr-automatic. Otherwise, for h and k multiplicatively independent, then a set is both h-automatic and k-automatic if and only if it is 1-automatic; that is, if and only if it is ultimately periodic.[24] This theorem is also due to Cobham,[25] with a multidimensional generalisation due to Semënov.[26][27]
If u(n) is a k-automatic sequence then the sequences u(kn) and u(kn − 1) are ultimately periodic.[28] Conversely, if v(n) is ultimately periodic then the sequence u defined by u(kn) = v(n) and otherwise zero is k-automatic.[29]
Let u(n) be a k-automatic sequence over the alphabet A. If f is a uniform morphism from A∗ to B∗ then the word f(u) is k-automatic sequence over the alphabet B.[30]
Let u(n) be a sequence over the alphabet A and suppose that there is an injective function j from A to the finite field Fq. The associated formal power series is
The sequence u is q-automatic if and only if the power series fu is algebraic over the rational function field Fq(z).[31]
Every automatic sequence is a morphic word.[32]
1-automatic sequences
k-automatic sequences are normally only defined for k 2.[1] The concept can be extended to k = 1 by defining a 1-automatic sequence to be a sequence whose n-th term depends on the unary notation for n; that is, (1)n. Since a finite state automaton must eventually return to a previously visited state, all 1-automatic sequences are eventually periodic.
Generalizations
k-automatic sequences are generalized to infinite alphabets by k-regular sequences.
See also
Notes
- ^ a b c d Allouche & Shallit (2003) p. 152
- ^ a b c Berstel et al (2009) p. 78
- ^ Allouche & Shallit (2003) p. 168
- ^ a b c Pytheas Fogg (2002) p. 13
- ^ Pytheas Fogg (2002) p. 15
- ^ Allouche & Shallit (2003) p. 212
- ^ Allouche & Shallit (2003) p. 175
- ^ Allouche & Shallit (2003) p. 185
- ^ Lothaire (2005) p. 527
- ^ Berstel & Reutenauer (2011) p. 91
- ^ Büchi, Julius Richard (1960). "Weak second-order arithmetic and finite automata". Z. Math. Logik Grundlagen Math. 6: 66–92. doi:10.1007/978-1-4613-8928-6_22.
- ^ Cobham, Alan (1972). "Uniform tag sequences". Math. Systems Theory. 6: 164–192. doi:10.1007/BF01706087.
- ^ 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.
- ^ Lothaire (2005) p. 528
- ^ a b Lothaire (2005) p. 525
- ^ a b Berstel & Reutenauer (2011) p. 92
- ^ Berstel & Reutenauer (2011) p. 94
- ^ Allouche & Shallit (2003) p. 154
- ^ Allouche & Shallit (2003) p. 156
- ^ Allouche & Shallit (2003) p. 155
- ^ Lothaire (2005) p. 526
- ^ Allouche & Shallit (2003) p. 183
- ^ Allouche & Shallit (2003) p. 176
- ^ Allouche & Shallit (2003) pp. 345–350
- ^ Cobham, Alan (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527.
- ^ Semenov, A. L. (1977). "Presburgerness of predicates regular in two number systems". Sibirsk. Mat. Zh. (in Russian). 18: 403–418.
- ^ Point, F.; Bruyère, V. (April 1997). "On the Cobham-Semenov theorem". Theory of Computing Systems. 30 (2): 197–220. doi:10.1007/BF02679449.
- ^ Lothaire (2005) p. 529
- ^ Berstel & Reutenauer (2011) p. 103
- ^ Lothaire (2005) p. 532
- ^ Berstel & Reutenauer (2011) p. 93
- ^ Lothaire (2005) p. 524
References
- 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.
- 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 0-521-84802-4. 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 3-540-44141-7. Zbl 1014.11015.
Further reading
- 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 0-521-33545-0. Zbl 0656.10032.
- Rowland, Eric (2015), "What is ... an automatic sequence?", Notices of the American Mathematical Society, 62: 274–276.
- 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 0-387-98824-6.