{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T05:04:27Z","timestamp":1768453467582,"version":"3.49.0"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,2]]},"abstract":"<jats:p>The neighbourhood of a language [Formula: see text] with respect to an additive distance consists of all strings that have distance at most the given radius from some string of [Formula: see text]. We show that the worst case deterministic state complexity of a radius [Formula: see text] neighbourhood of a language recognized by an [Formula: see text] state nondeterministic finite automaton [Formula: see text] is [Formula: see text]. In the case where [Formula: see text] is deterministic we get the same lower bound for the state complexity of the neighbourhood if we use an additive quasi-distance. The lower bound constructions use an alphabet of size linear in [Formula: see text]. We show that the worst case state complexity of the set of strings that contain a substring within distance [Formula: see text] from a string recognized by [Formula: see text] is [Formula: see text].<\/jats:p>","DOI":"10.1142\/s0129054118400099","type":"journal-article","created":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T07:34:45Z","timestamp":1523432085000},"page":"315-329","source":"Crossref","is-referenced-by-count":8,"title":["State Complexity of Neighbourhoods and Approximate Pattern Matching"],"prefix":"10.1142","volume":"29","author":[{"given":"Timothy","family":"Ng","sequence":"first","affiliation":[{"name":"School of Computing, Queen\u2019s University, Kingston, Ontario K7L 3N6, Canada"}]},{"given":"David","family":"Rappaport","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u2019s University, Kingston, Ontario K7L 3N6, Canada"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u2019s University, Kingston, Ontario K7L 3N6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2018,4,11]]},"reference":[{"key":"S0129054118400099BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.06.001"},{"key":"S0129054118400099BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.019"},{"key":"S0129054118400099BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"issue":"2","key":"S0129054118400099BIB005","first-page":"141","volume":"8","author":"Calude C. S.","year":"2002","journal-title":"J. Univ. Comput. Sci."},{"key":"S0129054118400099BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00234-2"},{"key":"S0129054118400099BIB008","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113400315"},{"key":"S0129054118400099BIB009","first-page":"293","volume":"9","author":"Kari L.","year":"2004","journal-title":"J. Automata, Languages, and Combinatorics"},{"key":"S0129054118400099BIB011","first-page":"278","volume":"8","author":"Konstantinidis S.","year":"2002","journal-title":"J. Univ. Comput. Sci."},{"key":"S0129054118400099BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.06.001"},{"key":"S0129054118400099BIB013","first-page":"55","volume":"13","author":"Konstantinidis S.","year":"2008","journal-title":"J. Automata, Languages, and Combinatorics"},{"key":"S0129054118400099BIB014","doi-asserted-by":"crossref","first-page":"257","DOI":"10.3233\/FI-2010-287","volume":"101","author":"Konstantinidis S.","year":"2010","journal-title":"Fundamenta Informaticae"},{"issue":"8","key":"S0129054118400099BIB015","first-page":"707","volume":"10","author":"Levenshtein V. I.","year":"1966","journal-title":"Soviet Physics Doklady"},{"key":"S0129054118400099BIB017","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2914"},{"key":"S0129054118400099BIB018","first-page":"509","volume-title":"Language and Automata Theory and Applications","author":"Povarov G.","year":"2007"},{"key":"S0129054118400099BIB019","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107005443"},{"key":"S0129054118400099BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s10032-002-0082-8"},{"key":"S0129054118400099BIB021","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"Shallit J.","year":"2009"},{"key":"S0129054118400099BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118400099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T13:59:28Z","timestamp":1604152768000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118400099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":18,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,4,11]]},"published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.1142\/S0129054118400099"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118400099","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}