Loading…
Periodicity, repetitions, and orbits of an automatic sequence
We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given k -automatic sequence is ultimately periodic. We prove that it is decidable whether a given k -automa...
Saved in:
| Published in: | Theoretical computer science 2009-08, Vol.410 (30), p.2795-2803 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c371t-8a26674a941c96c1910fc59d8ed5e9ec302c187dde05c2194999f3f2c0c1f5493 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c371t-8a26674a941c96c1910fc59d8ed5e9ec302c187dde05c2194999f3f2c0c1f5493 |
| container_end_page | 2803 |
| container_issue | 30 |
| container_start_page | 2795 |
| container_title | Theoretical computer science |
| container_volume | 410 |
| creator | Allouche, Jean-Paul Rampersad, Narad Shallit, Jeffrey |
| description | We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given
k
-automatic sequence is ultimately periodic. We prove that it is decidable whether a given
k
-automatic sequence is overlap-free (or squarefree, or cubefree, etc.). We prove that the lexicographically least sequence in the orbit closure of a
k
-automatic sequence is
k
-automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope
α
, have automatic continued fraction expansions if
α
does. |
| doi_str_mv | 10.1016/j.tcs.2009.02.006 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_34657048</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0304397509000942</els_id><sourcerecordid>34657048</sourcerecordid><originalsourceid>FETCH-LOGICAL-c371t-8a26674a941c96c1910fc59d8ed5e9ec302c187dde05c2194999f3f2c0c1f5493</originalsourceid><addsrcrecordid>eNp9kE1LAzEQhoMoWKs_wNuePHXXSTb7EcSDFL-goAc9hziZhZR2U5NU6L83ZT07l2HgfWfmfRi75lBx4O3tukoYKwGgKhAVQHvCZrzvVCmEkqdsBjXIslZdc84uYlxDrqZrZ-z-nYLz1qFLh0URaEfJJefHuCjMaAsfvlyKhR_yVJh98luTHBaRvvc0Il2ys8FsIl399Tn7fHr8WL6Uq7fn1-XDqsS646nsjWjbTholOaoWueIwYKNsT7YhRViDwPystQQNCq6kUmqoB4GAfGikqufsZtq7Cz5fjklvXUTabMxIfh91LdumA9lnIZ-EGHyMgQa9C25rwkFz0EdQeq0zKH0EpUHoDCp77iYP5QQ_joKO6I7prAuESVvv_nH_AsCDcFA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>34657048</pqid></control><display><type>article</type><title>Periodicity, repetitions, and orbits of an automatic sequence</title><source>ScienceDirect Journals</source><creator>Allouche, Jean-Paul ; Rampersad, Narad ; Shallit, Jeffrey</creator><creatorcontrib>Allouche, Jean-Paul ; Rampersad, Narad ; Shallit, Jeffrey</creatorcontrib><description>We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given
k
-automatic sequence is ultimately periodic. We prove that it is decidable whether a given
k
-automatic sequence is overlap-free (or squarefree, or cubefree, etc.). We prove that the lexicographically least sequence in the orbit closure of a
k
-automatic sequence is
k
-automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope
α
, have automatic continued fraction expansions if
α
does.</description><identifier>ISSN: 0304-3975</identifier><identifier>EISSN: 1879-2294</identifier><identifier>DOI: 10.1016/j.tcs.2009.02.006</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Automatic sequence ; Continued fraction ; Decidability ; Orbit ; Orbit closure ; Overlap-free ; Periodicity ; Rudin–Shapiro sequence ; Squarefree ; Thue–Morse sequence</subject><ispartof>Theoretical computer science, 2009-08, Vol.410 (30), p.2795-2803</ispartof><rights>2009 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c371t-8a26674a941c96c1910fc59d8ed5e9ec302c187dde05c2194999f3f2c0c1f5493</citedby><cites>FETCH-LOGICAL-c371t-8a26674a941c96c1910fc59d8ed5e9ec302c187dde05c2194999f3f2c0c1f5493</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Allouche, Jean-Paul</creatorcontrib><creatorcontrib>Rampersad, Narad</creatorcontrib><creatorcontrib>Shallit, Jeffrey</creatorcontrib><title>Periodicity, repetitions, and orbits of an automatic sequence</title><title>Theoretical computer science</title><description>We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given
k
-automatic sequence is ultimately periodic. We prove that it is decidable whether a given
k
-automatic sequence is overlap-free (or squarefree, or cubefree, etc.). We prove that the lexicographically least sequence in the orbit closure of a
k
-automatic sequence is
k
-automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope
α
, have automatic continued fraction expansions if
α
does.</description><subject>Automatic sequence</subject><subject>Continued fraction</subject><subject>Decidability</subject><subject>Orbit</subject><subject>Orbit closure</subject><subject>Overlap-free</subject><subject>Periodicity</subject><subject>Rudin–Shapiro sequence</subject><subject>Squarefree</subject><subject>Thue–Morse sequence</subject><issn>0304-3975</issn><issn>1879-2294</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2009</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LAzEQhoMoWKs_wNuePHXXSTb7EcSDFL-goAc9hziZhZR2U5NU6L83ZT07l2HgfWfmfRi75lBx4O3tukoYKwGgKhAVQHvCZrzvVCmEkqdsBjXIslZdc84uYlxDrqZrZ-z-nYLz1qFLh0URaEfJJefHuCjMaAsfvlyKhR_yVJh98luTHBaRvvc0Il2ys8FsIl399Tn7fHr8WL6Uq7fn1-XDqsS646nsjWjbTholOaoWueIwYKNsT7YhRViDwPystQQNCq6kUmqoB4GAfGikqufsZtq7Cz5fjklvXUTabMxIfh91LdumA9lnIZ-EGHyMgQa9C25rwkFz0EdQeq0zKH0EpUHoDCp77iYP5QQ_joKO6I7prAuESVvv_nH_AsCDcFA</recordid><startdate>20090820</startdate><enddate>20090820</enddate><creator>Allouche, Jean-Paul</creator><creator>Rampersad, Narad</creator><creator>Shallit, Jeffrey</creator><general>Elsevier B.V</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20090820</creationdate><title>Periodicity, repetitions, and orbits of an automatic sequence</title><author>Allouche, Jean-Paul ; Rampersad, Narad ; Shallit, Jeffrey</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c371t-8a26674a941c96c1910fc59d8ed5e9ec302c187dde05c2194999f3f2c0c1f5493</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Automatic sequence</topic><topic>Continued fraction</topic><topic>Decidability</topic><topic>Orbit</topic><topic>Orbit closure</topic><topic>Overlap-free</topic><topic>Periodicity</topic><topic>Rudin–Shapiro sequence</topic><topic>Squarefree</topic><topic>Thue–Morse sequence</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Allouche, Jean-Paul</creatorcontrib><creatorcontrib>Rampersad, Narad</creatorcontrib><creatorcontrib>Shallit, Jeffrey</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Allouche, Jean-Paul</au><au>Rampersad, Narad</au><au>Shallit, Jeffrey</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Periodicity, repetitions, and orbits of an automatic sequence</atitle><jtitle>Theoretical computer science</jtitle><date>2009-08-20</date><risdate>2009</risdate><volume>410</volume><issue>30</issue><spage>2795</spage><epage>2803</epage><pages>2795-2803</pages><issn>0304-3975</issn><eissn>1879-2294</eissn><abstract>We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given
k
-automatic sequence is ultimately periodic. We prove that it is decidable whether a given
k
-automatic sequence is overlap-free (or squarefree, or cubefree, etc.). We prove that the lexicographically least sequence in the orbit closure of a
k
-automatic sequence is
k
-automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope
α
, have automatic continued fraction expansions if
α
does.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.tcs.2009.02.006</doi><tpages>9</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0304-3975 |
| ispartof | Theoretical computer science, 2009-08, Vol.410 (30), p.2795-2803 |
| issn | 0304-3975 1879-2294 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_34657048 |
| source | ScienceDirect Journals |
| subjects | Automatic sequence Continued fraction Decidability Orbit Orbit closure Overlap-free Periodicity Rudin–Shapiro sequence Squarefree Thue–Morse sequence |
| title | Periodicity, repetitions, and orbits of an automatic sequence |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T20%3A54%3A30IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Periodicity,%20repetitions,%20and%20orbits%20of%20an%20automatic%20sequence&rft.jtitle=Theoretical%20computer%20science&rft.au=Allouche,%20Jean-Paul&rft.date=2009-08-20&rft.volume=410&rft.issue=30&rft.spage=2795&rft.epage=2803&rft.pages=2795-2803&rft.issn=0304-3975&rft.eissn=1879-2294&rft_id=info:doi/10.1016/j.tcs.2009.02.006&rft_dat=%3Cproquest_cross%3E34657048%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c371t-8a26674a941c96c1910fc59d8ed5e9ec302c187dde05c2194999f3f2c0c1f5493%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=34657048&rft_id=info:pmid/&rfr_iscdi=true |