{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:16Z","timestamp":1740133936327,"version":"3.37.3"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:p>A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. This paper addresses a new problem by extending the closed string problem to the [Formula: see text]-closed string problem, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter [Formula: see text].<\/jats:p><jats:p>We address the problem of deciding whether or not a given string of length [Formula: see text] over an integer alphabet is [Formula: see text]-closed and additionally specifying the border resulting in the string being [Formula: see text]-closed. Specifically, we present an [Formula: see text]-time and [Formula: see text]-space algorithm to achieve this along with the pseudocode of an implementation and proof-of-concept experimental results.<\/jats:p>","DOI":"10.1142\/s0129054120500288","type":"journal-article","created":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T14:56:32Z","timestamp":1598453792000},"page":"595-610","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Identification of k-Closed Strings"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3157-8086","authenticated-orcid":false,"given":"Hayam","family":"Alamro","sequence":"first","affiliation":[{"name":"Department of Informatics, King\u2019s College London, London, UK"},{"name":"Department of Information Systems, Princess Nourah bint Abdulrahman University, Riyadh, KSA"}]},{"given":"Mai","family":"Alzamel","sequence":"additional","affiliation":[{"name":"Department of Informatics, King\u2019s College London, London, UK"},{"name":"Department of Computer Science, King Saud University, Riyadh, KSA"}]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[{"name":"Department of Informatics, King\u2019s College London, London, UK"}]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7806-7086","authenticated-orcid":false,"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National University of Singapore, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1644-041X","authenticated-orcid":false,"given":"Steven","family":"Watts","sequence":"additional","affiliation":[{"name":"Department of Informatics, King\u2019s College London, London, UK"}]}],"member":"219","published-online":{"date-parts":[[2020,8,26]]},"reference":[{"key":"S0129054120500288BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-65172-9_49"},{"key":"S0129054120500288BIB002","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-017-0094-z"},{"key":"S0129054120500288BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78825-8_28"},{"key":"S0129054120500288BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.04.009"},{"key":"S0129054120500288BIB005","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/978-3-319-15579-1_29","volume-title":"Language and Automata Theory and Applications","author":"Badkobeh G.","year":"2015"},{"key":"S0129054120500288BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19315-1_5"},{"key":"S0129054120500288BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"S0129054120500288BIB008","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853"},{"key":"S0129054120500288BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646102"},{"key":"S0129054120500288BIB010","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.63.18"},{"key":"S0129054120500288BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/8307.8309"},{"key":"S0129054120500288BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"S0129054120500288BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90178-7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500288","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T09:36:57Z","timestamp":1696585017000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500288"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8]]},"references-count":13,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["10.1142\/S0129054120500288"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500288","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2020,8]]}}}