{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T22:29:24Z","timestamp":1791412164779,"version":"4.3.3"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["DNRF-2020R1A4A3079947"],"award-info":[{"award-number":["DNRF-2020R1A4A3079947"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["OGP0147224"],"award-info":[{"award-number":["OGP0147224"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p> The [Formula: see text]-prefix-free, [Formula: see text]-suffix-free and [Formula: see text]-infix-free languages generalize the prefix-free, suffix-free and infix-free languages by allowing marginal errors. For example, a string [Formula: see text] in a [Formula: see text]-prefix-free language [Formula: see text] can be a prefix of up to [Formula: see text] different strings in [Formula: see text]. We also define finitely prefix-free languages in which a string [Formula: see text] can be a prefix of finitely many strings. We present efficient algorithms that determine whether or not a given regular language is [Formula: see text]-prefix-free, [Formula: see text]-suffix-free or [Formula: see text]-infix-free, and analyze the time complexity of the algorithms. We establish undecidability results for deciding these properties for (linear) context-free languages. <\/jats:p>","DOI":"10.1142\/s0129054121410057","type":"journal-article","created":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T15:09:30Z","timestamp":1614092970000},"page":"509-529","source":"Crossref","is-referenced-by-count":5,"title":["Generalizations of Code Languages with Marginal Errors"],"prefix":"10.1142","volume":"32","author":[{"given":"Sang-Ki","family":"Ko","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Kangwon National University, Gangwon 24341, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, Seoul 03722, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u2019s University, Kingston, Ontario K7L 3N6, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"issue":"1","key":"S0129054121410057BIB001","first-page":"121","volume":"56","author":"B\u00e9al M.-P.","year":"2002","journal-title":"Fundamenta Informaticae"},{"key":"S0129054121410057BIB002","volume-title":"Theory of Codes","author":"Berstel J.","year":"1985"},{"key":"S0129054121410057BIB003","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195768"},{"key":"S0129054121410057BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90260-9"},{"key":"S0129054121410057BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-015-9502-9"},{"key":"S0129054121410057BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21819-9_11"},{"key":"S0129054121410057BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.016"},{"key":"S0129054121410057BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256174"},{"key":"S0129054121410057BIB009","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"S0129054121410057BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00104-5"},{"key":"S0129054121410057BIB011","first-page":"118","volume":"93","author":"Han Y.-S.","year":"2007","journal-title":"Bull. European Assoc. Theoret. Comput. Sci."},{"key":"S0129054121410057BIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113500238"},{"issue":"16","key":"S0129054121410057BIB013","first-page":"113","volume":"76","author":"Han Y.-S.","year":"2007","journal-title":"Fundamenta Informaticae"},{"key":"S0129054121410057BIB014","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106003887"},{"key":"S0129054121410057BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.10.017"},{"key":"S0129054121410057BIB016","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"2006","edition":"3"},{"key":"S0129054121410057BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"S0129054121410057BIB018","series-title":"Handbook of Formal Languages","first-page":"511","volume-title":"Word, Language, Grammar","volume":"1","author":"J\u00fcrgensen H.","year":"1997"},{"key":"S0129054121410057BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.015"},{"key":"S0129054121410057BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/11925903_10"},{"key":"S0129054121410057BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04921-2_39"},{"key":"S0129054121410057BIB022","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.16"},{"key":"S0129054121410057BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/PL00006033"},{"key":"S0129054121410057BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00300-8"},{"key":"S0129054121410057BIB025","doi-asserted-by":"publisher","DOI":"10.1089\/10665270152530818"},{"key":"S0129054121410057BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90028-2"},{"key":"S0129054121410057BIB027","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"S0129054121410057BIB028","volume-title":"Theory of Computation","author":"Wood D.","year":"1987"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121410057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T01:44:26Z","timestamp":1628732666000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121410057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,22]]},"references-count":28,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1142\/S0129054121410057"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121410057","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,22]]}}}