Automatic sequence: Difference between revisions

Revision as of 19:46, 10 February 2018

Revision as of 11:00, 15 February 2019

Line 41:

Let ''u''(''n'') be a sequence over an alphabet Σ and suppose that there is an [[injective function]] β from Σ to the [[finite field]] '''F'''_''q'', where ''q'' = ''p''^''n'' for some prime ''p''. The associated [[formal power series]] is

:<math> \sum_{i \geq 0} \beta(u(i)) X^i . </math>

Then the sequence ''u'' is ''q''-automatic if and only if this formal power series is [[Algebraic function|algebraic]] over '''F'''_''q''(''X''). This result is due to Christol, and it is referred to in the literature as ''Christol's theorem''.<ref>{{cite journal | first=G. | last=Christol | title=Ensembles presque périodiques ''k''-reconnaissables | journal=Theoret. Comput. Sci. | volume=9 | year=1979 | pages=141–145 | doi=10.1016/0304-3975(79)90011-2 }}</ref>

==History==

Automatic sequences were introduced by [[Julius Richard Büchi|Büchi]] in 1960,<ref>{{cite journalbook | first=J. R. | 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 | isbn=978-1-4613-8930-9 }}</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 name=C72/>

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’anneaul'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==

Line 79:

*Every automatic sequence is a [[morphic word]].<ref name=LotIII524>Lothaire (2005) p.&nbsp;524</ref>

*For ''k''&nbsp;≥&nbsp;2 and ''r''&nbsp;≥&nbsp;1, a sequence is ''k''-automatic if and only if it is ''k''^''r''-automatic. This result is due to Eilenberg.<ref>{{cite book | last=Eilenberg | first=Samuel | title=Automata, languages, and machines | volume=A | ___location=Orlando | publisher=[[Academic Press]] | year=1974 | isbn=978-0-122-34001-97 }}</ref>

*For ''h'' and ''k'' [[Multiplicative independence|multiplicatively independent]], a sequence is both ''h''-automatic and ''k''-automatic if and only if it is ultimately periodic.<ref name=as345>Allouche & Shallit (2003) pp.&nbsp;345–350</ref> This result is due to Cobham,<ref>{{cite journal | first=A. | last=Cobham | title=On the base-dependence of sets of numbers recognizable by finite automata | journal=Math. Systems Theory | volume=3 | issue=2 | year=1969 | pages=186–192 | doi=10.1007/BF01746527 }}</ref> with a multidimensional generalisation due to Semenov.<ref>{{cite journal | first=A. L. | last=Semenov | title=Presburgerness of predicates regular in two number systems | language=Russian | journal=Sibirsk. Mat. Zh. | volume=18 | year=1977 | pages=403–418 }}</ref><ref>{{ cite journal | journal=Theory of Computing Systems | date=1997 | volume=30 | number=2 | pages=197–220 | title=On the Cobham-Semenov theorem | first1=F. | last1=Point | first2=V. | last2=Bruyère | doi=10.1007/BF02679449 }}</ref>

*If ''u''(''n'') is a ''k''-automatic sequence over an alphabet Σ and ''f'' is a [[uniform morphism]] from Σ^&lowast; to another alphabet Δ^&lowast;, then ''f''(''u'') is a ''k''-automatic sequence over Δ.<ref name=ApCoW532>Lothaire (2005) p.&nbsp;532</ref>

Line 92:

The ___domain of an automatic sequence can be extended from the natural numbers to the integers via ''two-sided'' automatic sequences. This stems from the fact that, given ''k''&nbsp;≥&nbsp;2, every integer can be represented uniquely in the form <math> \sum_{0 \leq i \leq r} a_{i}(-k)^{i} , </math> where <math>a_{i} \in \{0, \dots, k-1\}</math>. Then a two-sided infinite sequence ''a''(''n'')_{''n''&nbsp;<math>\in \mathbb{Z}</math>} is (−''k'')-automatic if and only if its subsequences ''a''(''n'')_{n ≥ 0} and ''a''(−''n'')_{n ≥ 0} are ''k''-automatic.<ref name=AS162>Allouche & Shallit (2003) p.&nbsp;162</ref>

The alphabet of a ''k''-automatic sequence can be extended from finite size to infinite size via [[k-regular sequence|''k''-regular sequences]].<ref>{{citation | last1 = Allouche | first1 = J.-P. | last2 = Shallit | first2 = J. | title = The ring of ''k''-regular sequences | journal = Theoret. Comput. Sci. | volume = 98 | issue = 2 | year = 1992 | pages = 163–197 | doi=10.1016/0304-3975(92)90001-v}}</ref>

==See also==

Line 104:

* {{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 journal | last=Cobham | first=Alan | title=Uniform tag sequences | journal=Math. Systems Theory | volume=6 | issue=1–2 | year=1972 | pages=164–192 | doi=10.1007/BF01706087 }}

*{{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=978-0-521-84802-42 | zbl=1133.68067 }}

* {{cite book | last=Pytheas Fogg | first=N. | others=Editors [[Valérie Berthé|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=978-3-540-44141-70 | 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=978-0-521-33545-04 | zbl=0656.10032 }}

*{{citation | last = Rowland | first = Eric | title = What is ... an automatic sequence? | journal = Notices of the American Mathematical Society | volume = 62 | issue = 3 | year = 2015 | pages = 274–276 | urldoi = https://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=978-0-387-98824-65 | last=Shallit | first=Jeffrey | author1-link=Jeffrey Shallit | chapter=Number theory and formal languages | pages=547–570 }}

{{DEFAULTSORT:Automatic Sequence}}