{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:24:46Z","timestamp":1758273886383},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,6]]},"abstract":"<jats:p> We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length \u2264 1, or has a privileged border that occurs exactly twice in w. We prove the following results: (1) if w<jats:sup>k<\/jats:sup> is privileged for some [Formula: see text], then w<jats:sup>j<\/jats:sup> is privileged for all [Formula: see text]; (2) the language of privileged words is not context-free; (3) there is a linear-time algorithm to check if a given word is privileged; and (4) there are at least [Formula: see text] privileged binary words of length n. <\/jats:p>","DOI":"10.1142\/s0129054116500088","type":"journal-article","created":{"date-parts":[[2016,7,7]],"date-time":"2016-07-07T07:21:04Z","timestamp":1467876064000},"page":"431-442","source":"Crossref","is-referenced-by-count":3,"title":["Remarks on Privileged Words"],"prefix":"10.1142","volume":"27","author":[{"given":"Michael","family":"Forsyth","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada"}]},{"given":"Amlesh","family":"Jayakumar","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada"}]},{"given":"Jarkko","family":"Peltom\u00e4ki","sequence":"additional","affiliation":[{"name":"Turku Centre for Computer Science TUCS, 20520 Turku, Finland"},{"name":"Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland"}]},{"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada"}]}],"member":"219","published-online":{"date-parts":[[2016,7,7]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-15579-1_29"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2013.01.002"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2013.08.026"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694004"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.028"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116500088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:32:29Z","timestamp":1565199149000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116500088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6]]},"references-count":6,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2016,7,7]]},"published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1142\/S0129054116500088"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116500088","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6]]}}}