{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T05:09:36Z","timestamp":1772860176914,"version":"3.50.1"},"reference-count":10,"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":[[2018,8]]},"abstract":"<jats:p>We contribute to the study of square-free words. The classical notion of a square-free word has a natural generalization to partial words, studied in several papers since 2008. We prove that the maximal density of wildcards in the ternary infinite square-free partial word is surprisingly big: [Formula: see text]. Further we show that the density of wildcards in a finitary infinite square-free partial words is at most [Formula: see text] and this bound is reached by a quaternary word. We demonstrate that partial square-free words can be viewed as \u201cusual\u201d square-free words with some letters replaced by wildcards and introduce the corresponding characteristic of infinite square-free words, called flexibility. The flexibility is estimated for some important words and classes of words; an interesting phenomenon is the existence of \u201crigid\u201d square-free words, having no room for wildcards at all.<\/jats:p>","DOI":"10.1142\/s0129054118420078","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T10:47:08Z","timestamp":1534848428000},"page":"845-860","source":"Crossref","is-referenced-by-count":1,"title":["Square-Free Partial Words with Many Wildcards"],"prefix":"10.1142","volume":"29","author":[{"given":"Daniil","family":"Gasnikov","sequence":"first","affiliation":[{"name":"Department of Algebra and Fundamental Informatics, Ural Federal University, Ekaterinburg, Russia"}]},{"given":"Arseny M.","family":"Shur","sequence":"additional","affiliation":[{"name":"Department of Algebra and Fundamental Informatics, Ural Federal University, Ekaterinburg, Russia"}]}],"member":"219","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"S0129054118420078BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00255-2"},{"key":"S0129054118420078BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00407-2"},{"key":"S0129054118420078BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.11.006"},{"key":"S0129054118420078BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90011-8"},{"key":"S0129054118420078BIB007","first-page":"113","volume":"7","author":"Fischer M.","year":"1974","journal-title":"SIAM-AMS Proceedings"},{"key":"S0129054118420078BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.06.001"},{"key":"S0129054118420078BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.028"},{"issue":"1","key":"S0129054118420078BIB014","doi-asserted-by":"crossref","first-page":"P1.18","DOI":"10.37236\/5424","volume":"23","author":"Petrova E. A.","year":"2016","journal-title":"Electr. J. Comb."},{"key":"S0129054118420078BIB015","doi-asserted-by":"crossref","first-page":"R140","DOI":"10.37236\/412","volume":"17","author":"Shur A. M.","year":"2010","journal-title":"Electronic J. Combinatorics"},{"key":"S0129054118420078BIB017","first-page":"1","volume":"1","author":"Thue A.","year":"1912","journal-title":"Norske vid. Selsk. Skr. Mat. Nat. Kl."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118420078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T02:09:57Z","timestamp":1604801397000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118420078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":10,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,8,21]]},"published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.1142\/S0129054118420078"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118420078","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}