{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:22:06Z","timestamp":1776316926910,"version":"3.50.1"},"reference-count":26,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,10]]},"abstract":"<jats:p>A pure morphic sequence is a right-infinite, symbolic sequence obtained by iterating a letter-to-word substitution. For instance, the Fibonacci sequence and the Thue\u2013Morse sequence, which play an important role in theoretical computer science, are pure morphic. Define a coding as a letter-to-letter substitution. The image of a pure morphic sequence under a coding is called a morphic sequence.<\/jats:p><jats:p>A sequence x is called uniformly recurrent if for each finite subword u of x there exists an integer l such that u occurs in every l-length subword of x.<\/jats:p><jats:p>The paper mainly focuses on the problem of deciding whether a given morphic sequence is uniformly recurrent. Although the status of the problem remains open, we show some evidence for its decidability: in particular, we prove that it can be solved in polynomial time on pure morphic sequences and on automatic sequences.<\/jats:p><jats:p>In addition, we prove that the complexity of every uniformly recurrent, morphic sequence has at most linear growth: here, complexity is understood as the function that maps each positive integer n to the number of distinct n-length subwords occurring in the sequence.<\/jats:p>","DOI":"10.1142\/s0129054109006966","type":"journal-article","created":{"date-parts":[[2009,9,23]],"date-time":"2009-09-23T15:33:52Z","timestamp":1253720032000},"page":"919-940","source":"Crossref","is-referenced-by-count":7,"title":["ON UNIFORMLY RECURRENT MORPHIC SEQUENCES"],"prefix":"10.1142","volume":"20","author":[{"given":"FRANCOIS","family":"NICOLAS","sequence":"first","affiliation":[{"name":"Department of Computer Science, P. O. Box 68, 00014 University of Helsinki, Finland"}]},{"given":"YURI","family":"PRITYKIN","sequence":"additional","affiliation":[{"name":"Moscow State University, Department of Mechanics and Mathematics, Mathematical Logic and Theory of Algorithms Division, Leninskie gory, Moscow, 119991, Russia"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","first-page":"133","DOI":"10.36045\/bbms\/1103408543","volume":"1","author":"Allouche J.-P.","journal-title":"Bulletin of the Belgian Mathematical Society\u2014Simon Stevin"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546563"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3139"},{"key":"rf4","doi-asserted-by":"crossref","first-page":"661","DOI":"10.36045\/bbms\/1074791324","volume":"10","author":"Cassaigne J.","journal-title":"Bulletin of the Belgian Mathematical Society\u2013Simon Stevin"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01706087"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/62.2161"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90254-2"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80028-X"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00400-2"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/BF00537161"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_7"},{"key":"rf13","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1051\/ita\/1986200100471","volume":"20","author":"Harju T.","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004620"},{"key":"rf15","series-title":"Selecta Mathematica II","volume-title":"Maschinenerzeugte 0-1-Folgen","author":"Jacobs K.","year":"1970"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00101-2"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.2307\/2371264"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00847-2"},{"key":"rf22","first-page":"55","volume":"26","author":"Pansiot J.-J.","journal-title":"Bulletin of the European Association of Theoretical Computer Science"},{"key":"rf23","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1051\/ita\/1986200100431","volume":"20","author":"Pansiot J.-J.","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/b13861"},{"key":"rf29","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0081890","volume-title":"Substitution Dynamical Systems\u2014Spectral Analysis","volume":"1284","author":"Queff\u00e9lec M.","year":"1987"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1070\/IM1984v022n03ABEH001456"},{"key":"rf33","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"2005"},{"key":"rf34","unstructured":"W.\u00a0Thomas, Handbook of Theoretical Computer Science, ed. J.\u00a0van Leeuwen (Elsevier, 1990)\u00a0pp. 133\u2013191."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054109006966","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,22]],"date-time":"2020-05-22T11:42:38Z","timestamp":1590147758000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054109006966"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":26,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1142\/S0129054109006966"],"URL":"https:\/\/doi.org\/10.1142\/s0129054109006966","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10]]}}}