{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T22:26:28Z","timestamp":1649111188626},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> The neighbourhood of a regular language with respect to the prefix, suffix and subword distance is always regular and a tight bound for the state complexity of prefix distance neighbourhoods is known. We give upper bounds for the state complexity of the neighbourhood of radius [Formula: see text] of an [Formula: see text]-state deterministic finite automaton language with respect to the suffix distance and the subword distance, respectively. For restricted values of [Formula: see text] and [Formula: see text] we give a matching lower bound for the state complexity of suffix distance neighbourhoods. <\/jats:p>","DOI":"10.1142\/s0129054119400355","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1197-1216","source":"Crossref","is-referenced-by-count":0,"title":["State Complexity of Suffix Distance"],"prefix":"10.1142","volume":"30","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":[[2019,9,19]]},"reference":[{"key":"S0129054119400355BIB001","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2006010"},{"key":"S0129054119400355BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9515-7"},{"issue":"2","key":"S0129054119400355BIB003","first-page":"141","volume":"8","author":"Calude C. S.","year":"2002","journal-title":"Journal of Universal Computer Science"},{"key":"S0129054119400355BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00238-9"},{"key":"S0129054119400355BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00234-2"},{"issue":"4","key":"S0129054119400355BIB006","first-page":"251","volume":"21","author":"Gao Y.","year":"2016","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054119400355BIB007","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113400315"},{"key":"S0129054119400355BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.013"},{"issue":"2","key":"S0129054119400355BIB009","first-page":"293","volume":"9","author":"Kari L.","year":"2004","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054119400355BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.06.001"},{"key":"S0129054119400355BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04298-5_37"},{"key":"S0129054119400355BIB013","first-page":"70","volume":"111","author":"Kutrib M.","year":"2013","journal-title":"Bulletin of the EATCS"},{"key":"S0129054119400355BIB014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107341005"},{"key":"S0129054119400355BIB015","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118400099"},{"key":"S0129054119400355BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46376-6_6"},{"key":"S0129054119400355BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.05.018"},{"issue":"1","key":"S0129054119400355BIB018","first-page":"169","volume":"22","author":"Ng T.","year":"2017","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054119400355BIB019","first-page":"509","volume-title":"LATA 2007 Proceedings of the 1st International Conference on Language and Automata Theory and Applications","author":"Povarov G.","year":"2007"},{"key":"S0129054119400355BIB020","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"Shallit J.","year":"2009"},{"key":"S0129054119400355BIB021","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\/S0129054119400355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:07:01Z","timestamp":1568876821000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":20,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400355"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400355","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}