{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:44:09Z","timestamp":1648809849443},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p> This work answers some questions proposed by Bottoni, Labella, and Mitrana (Theoretical Computer Science 682, 2017) regarding the prefix\u2013suffix reduction on words. The operation is defined as a reduction by one half of every square that is present as either a prefix or a suffix of a word, leading thus to a finite set of words associated to the starting one. The iterated case considers consecutive applications of the operations, on all the resulting words. We show that the classes of linear and context-free language are closed under iterated bounded prefix\u2013suffix square reduction, and that for a given word we can determine in [Formula: see text] time all of its primitive prefix\u2013suffix square roots. <\/jats:p>","DOI":"10.1142\/s0129054120400067","type":"journal-article","created":{"date-parts":[[2020,1,31]],"date-time":"2020-01-31T06:55:02Z","timestamp":1580453702000},"page":"91-102","source":"Crossref","is-referenced-by-count":0,"title":["On the Prefix\u2013Suffix Duplication Reduction"],"prefix":"10.1142","volume":"31","author":[{"given":"Szil\u00e1rd Zsolt","family":"Fazekas","sequence":"first","affiliation":[{"name":"Department of Mathematical Science and Electrical-Electronic-Computer Engineering, Akita University, Japan"}]},{"given":"Robert","family":"Merca\u015f","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Loughborough University, UK"}]},{"given":"Daniel","family":"Reidenbach","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Loughborough University, UK"}]}],"member":"219","published-online":{"date-parts":[[2020,1,29]]},"reference":[{"key":"S0129054120400067BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.12.005"},{"key":"S0129054120400067BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90050-6"},{"key":"S0129054120400067BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90024-7"},{"key":"S0129054120400067BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190846"},{"key":"S0129054120400067BIB005","first-page":"133","volume":"69","author":"Dassow J.","year":"1999","journal-title":"Bulletin of EATCS"},{"key":"S0129054120400067BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054115400079"},{"key":"S0129054120400067BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23660-5_13"},{"key":"S0129054120400067BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23826-5_6"},{"key":"S0129054120400067BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90129-X"},{"key":"S0129054120400067BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.02.011"},{"key":"S0129054120400067BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/11779148_22"},{"key":"S0129054120400067BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73208-2_28"},{"key":"S0129054120400067BIB013","series-title":"LNCS","first-page":"297","volume-title":"Aspects of Molecular Computing. Essays in Honour of Tom Head on his 70th Birthday","volume":"2950","author":"Leupold P.","year":"2004"},{"key":"S0129054120400067BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.10.003"},{"key":"S0129054120400067BIB015","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1995"},{"key":"S0129054120400067BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"S0129054120400067BIB017","first-page":"1","volume":"7","author":"Thue A.","year":"1906","journal-title":"Norske vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana"},{"key":"S0129054120400067BIB018","volume":"1","author":"Thue A.","year":"1912","journal-title":"Norske vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana"},{"key":"S0129054120400067BIB019","first-page":"162","volume":"70","author":"Wang M.-W.","year":"2000","journal-title":"Bulletin of EATCS"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120400067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,31]],"date-time":"2020-01-31T06:55:10Z","timestamp":1580453710000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120400067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":19,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1142\/S0129054120400067"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120400067","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}