{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:55:50Z","timestamp":1760234150808,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:00:00Z","timestamp":1618876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ministry of Science and Higher Education of the Russian Federation","award":["Ural Mathematical Center project No. 075-02-2020-1537\/1"],"award-info":[{"award-number":["Ural Mathematical Center project No. 075-02-2020-1537\/1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Binary cube-free language and ternary square-free language are two \u201ccanonical\u201d representatives of a wide class of languages defined by avoidance properties. Each of these two languages can be viewed as an infinite binary tree reflecting the prefix order of its elements. We study how \u201chomogenious\u201d these trees are, analysing the following parameter: the density of branching nodes along infinite paths. We present combinatorial results and an efficient search algorithm, which together allowed us to get the following numerical results for the cube-free language: the minimal density of branching points is between 3509\/9120\u22480.38476 and 13\/29\u22480.44828, and the maximal density is between 0.72 and 67\/93\u22480.72043. We also prove the lower bound 223\/868\u22480.25691 on the density of branching points in the tree of the ternary square-free language.<\/jats:p>","DOI":"10.3390\/a14040126","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T13:58:04Z","timestamp":1618927084000},"page":"126","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Branching Densities of Cube-Free and Square-Free Words"],"prefix":"10.3390","volume":"14","author":[{"given":"Elena A.","family":"Petrova","sequence":"first","affiliation":[{"name":"Department of Algebra and Fundamental Informatics, Ural Federal University, 620075 Yekaterinburg, Russia"}]},{"given":"Arseny M.","family":"Shur","sequence":"additional","affiliation":[{"name":"Department of Algebra and Fundamental Informatics, Ural Federal University, 620075 Yekaterinburg, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,20]]},"reference":[{"key":"ref_1","first-page":"1","article-title":"\u00dcber unendliche Zeichenreihen","volume":"7","author":"Thue","year":"1906","journal-title":"Nor. Vid. Selsk. Skr. Mat. Nat. Kl."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/3-540-15641-0_35","article-title":"Overlap free words on two symbols","volume":"Volume 192","author":"Nivat","year":"1985","journal-title":"Automata on Infinite Words, Proceedings of the Ecole de Printemps d\u2019Informatique Theorique, Le Mont Dore, France, 14\u201318 May 1984"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1051\/ita\/2010012","article-title":"On the growth rates of complexity of threshold languages","volume":"44","author":"Shur","year":"2010","journal-title":"RAIRO Inform. Th\u00e9or. App."},{"key":"ref_4","first-page":"335","article-title":"Polynomial versus exponential growth in repetition-free binary words","volume":"104","author":"Shallit","year":"2004","journal-title":"J. Combin. Theory. Ser. A"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1051\/ita:2006020","article-title":"A generator of morphisms for infinite words","volume":"40","author":"Ochem","year":"2006","journal-title":"RAIRO Inform. Th\u00e9or. App."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"6507","DOI":"10.1016\/j.tcs.2011.08.006","article-title":"On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters","volume":"412","author":"Kolpakov","year":"2011","journal-title":"Theoret. Comput. Sci."},{"key":"ref_7","first-page":"801","article-title":"On two stronger versions of Dejean\u2019s conjecture","volume":"Volume 7464","author":"Tunev","year":"2012","journal-title":"Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012)"},{"key":"ref_8","first-page":"1","article-title":"The Number of Threshold Words on n Letters Grows Exponentially for Every n \u2265 27","volume":"23","author":"Currie","year":"2020","journal-title":"J. Integer Seq."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.cosrev.2012.09.001","article-title":"Growth properties of power-free languages","volume":"6","author":"Shur","year":"2012","journal-title":"Comput. Sci. Rev."},{"key":"ref_10","first-page":"1","article-title":"\u00dcber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen","volume":"1","author":"Thue","year":"1912","journal-title":"Nor. Vid. Selsk. Skr. Mat. Nat. Kl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3670","DOI":"10.1016\/j.tcs.2009.04.022","article-title":"Overlap-free words and spectra of matrices","volume":"410","author":"Jungers","year":"2009","journal-title":"Theoret. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s10208-012-9121-0","article-title":"Exact Computation of Joint Spectral Characteristics of Linear Operators","volume":"13","author":"Guglielmi","year":"2013","journal-title":"Found. Comput. Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0020-0190(84)90082-6","article-title":"On the centers of the set of weakly square-free words on a two-letter alphabet","volume":"19","author":"Carpi","year":"1984","journal-title":"Inform. Process. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/s00233-012-9382-6","article-title":"Deciding context equivalence of binary overlap-free words in linear time","volume":"84","author":"Shur","year":"2012","journal-title":"Semigroup Forum"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"261","DOI":"10.2140\/pjm.1979.85.261","article-title":"Avoidable patterns in strings of symbols","volume":"85","author":"Bean","year":"1979","journal-title":"Pac. J. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0195-6698(95)90051-9","article-title":"On the structure and extendibility of k-power free words","volume":"16","author":"Currie","year":"1995","journal-title":"Eur. J. Comb."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1016\/S0195-6698(03)00044-1","article-title":"The set of k-power free words over \u03a3 is empty or perfect","volume":"24","author":"Currie","year":"2003","journal-title":"Eur. J. Comb."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Petrova, E.A., and Shur, A.M. (2012, January 27\u201331). Constructing premaximal ternary square-free words of any level. Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), Bratislava, Slovakia.","DOI":"10.1007\/978-3-642-32589-2_65"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/978-3-319-23660-5_19","article-title":"On the tree of ternary square-free words","volume":"Volume 9304","author":"Petrova","year":"2015","journal-title":"Combinatorics on Words, Proceedings of the 10th International Conference (WORDS 2015), Kiel, Germany, 14\u201317 September 2015"},{"key":"ref_20","first-page":"1","article-title":"Aperiodic words on three symbols. II","volume":"327","author":"Shelton","year":"1981","journal-title":"J. Reine Angew. Math."},{"key":"ref_21","first-page":"44","article-title":"Aperiodic words on three symbols. III","volume":"330","author":"Shelton","year":"1982","journal-title":"J. Reine Angew. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1595","DOI":"10.1142\/S0129054112400643","article-title":"Constructing premaximal binary cube-free words of any level","volume":"23","author":"Petrova","year":"2012","journal-title":"Internat. J. Found. Comp. Sci."},{"key":"ref_23","first-page":"296","article-title":"On the tree of binary cube-free words","volume":"Volume 10396","author":"Petrova","year":"2017","journal-title":"Developments in Language Theory, Proceedings of the 21st International Conference (DLT 2017), Li\u00e8ge, Belgium, 7\u201311 August 2017"},{"key":"ref_24","unstructured":"Lothaire, M. (1983). Combinatorics on Words; Volume 17, Encyclopedia of Mathematics and Its Applications, Addison-Wesley."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1307\/mmj\/1028998766","article-title":"The equation aM=bNcP in a free group","volume":"9","author":"Lyndon","year":"1962","journal-title":"Mich. Math. J."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","article-title":"Uniqueness theorems for periodic functions","volume":"16","author":"Fine","year":"1965","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0020-0190(98)00104-5","article-title":"Automata and forbidden words","volume":"67","author":"Crochemore","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"3209","DOI":"10.1016\/j.tcs.2010.05.017","article-title":"Growth rates of complexity of power-free languages","volume":"411","author":"Shur","year":"2010","journal-title":"Theoret. Comput. Sci."},{"key":"ref_29","first-page":"311","article-title":"Transition property for cube-free words","volume":"Volume 11532","author":"Petrova","year":"2019","journal-title":"Computer Science\u2014Theory and Applications, Proceedings of the 14th International Computer Science Symposium in Russia (CSR 2019), Novosibirsk, Russia, 1\u20135 July 2019"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","article-title":"A characterization of the minimum cycle mean in a digraph","volume":"23","author":"Karp","year":"1978","journal-title":"Discret. Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/126\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:50:23Z","timestamp":1760161823000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,20]]},"references-count":30,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["a14040126"],"URL":"https:\/\/doi.org\/10.3390\/a14040126","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,4,20]]}}}