{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T19:56:19Z","timestamp":1766087779503,"version":"3.44.0"},"reference-count":31,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T00:00:00Z","timestamp":1633910400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2022,1,12]]},"abstract":"<jats:p> In this paper, we discuss the addition of substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems, i.e., in addition to insertions and deletions we allow single letter replacements to occur. We investigate the effect of the addition of substitution rules on the context dependency of such systems, thereby also obtaining new characterizations of and even normal forms for context-sensitive (CS) and recursively enumerable (RE) languages and their phrase-structure grammars. More specifically, we prove that for each RE language, there is a system generating this language that only inserts and deletes strings of length two without considering the context of the insertion or deletion site, but which may change symbols (by a substitution operation) by checking a single symbol to the left of the substitution site. When we allow checking left and right single-letter context in substitutions, even context-free insertions and deletions of single letters suffice to reach computational completeness. When allowing context-free insertions only, checking left and right single-letter context in substitutions gives a new characterization of CS. This clearly shows the power of this new type of rules. <\/jats:p>","DOI":"10.3233\/com-210345","type":"journal-article","created":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T05:32:43Z","timestamp":1634103163000},"page":"57-83","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":2,"title":["Insertion-deletion systems with substitutions I"],"prefix":"10.1177","volume":"11","author":[{"given":"Martin","family":"Vu","sequence":"first","affiliation":[{"name":"Fachbereich 3 \u2013 Informatik, Universit\u00e4t Bremen, Germany."}]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[{"name":"Fachbereich 4 \u2013 Abteilung Informatikwissenschaften, Universit\u00e4t Trier, Germany."}]}],"member":"179","published-online":{"date-parts":[[2021,10,11]]},"reference":[{"doi-asserted-by":"publisher","key":"ref001","DOI":"10.1126\/science.7973651"},{"doi-asserted-by":"publisher","key":"ref002","DOI":"10.1142\/9781848165458_0009"},{"doi-asserted-by":"publisher","key":"ref003","DOI":"10.1089\/cmb.1995.2.1"},{"doi-asserted-by":"publisher","key":"ref004","DOI":"10.1007\/978-3-030-81508-0_2"},{"doi-asserted-by":"publisher","key":"ref005","DOI":"10.1007\/s002240000112"},{"doi-asserted-by":"publisher","key":"ref006","DOI":"10.1007\/s11047-013-9396-3"},{"doi-asserted-by":"publisher","key":"ref007","DOI":"10.1002\/cfg.364"},{"doi-asserted-by":"publisher","key":"ref008","DOI":"10.1016\/0020-0255(83)90023-3"},{"doi-asserted-by":"publisher","key":"ref009","DOI":"10.1016\/S0092-8240(87)90018-8"},{"doi-asserted-by":"publisher","key":"ref010","DOI":"10.1016\/S0303-2647(00)00091-5"},{"unstructured":"L.\u00a0Kari, On insertions and deletions in formal languages, PhD thesis, University of Turku, Finland, 1991.","key":"ref011"},{"doi-asserted-by":"publisher","key":"ref012","DOI":"10.1007\/BF03024425"},{"doi-asserted-by":"publisher","key":"ref013","DOI":"10.1007\/978-3-540-88282-4_31"},{"unstructured":"A.\u00a0Krassovitskiy, Y.\u00a0Rogozhin and S.\u00a0Verlan, One-sided insertion and deletion: Traditional and P systems case, in: International Workshop on Computing with Biomolecules, E.\u00a0Csuhaj-Varj\u00fa, R.\u00a0Freund, M.\u00a0Oswald and K.\u00a0Salomaa, eds, Vol.\u00a0244, \u00d6sterreichische Computer Gesellschaft OCG, 2008, pp.\u00a053\u201364, https:\/\/hal.archives-ouvertes.fr\/hal-01352396.","key":"ref014"},{"doi-asserted-by":"publisher","key":"ref015","DOI":"10.1007\/s11047-010-9208-y"},{"doi-asserted-by":"publisher","key":"ref016","DOI":"10.3115\/990403.990451"},{"doi-asserted-by":"publisher","key":"ref017","DOI":"10.1016\/j.tcs.2004.06.031"},{"doi-asserted-by":"publisher","key":"ref018","DOI":"10.1007\/978-3-540-74593-8_18"},{"doi-asserted-by":"publisher","key":"ref019","DOI":"10.1126\/science.278.5337.446"},{"key":"ref020","first-page":"263","volume":"52","author":"P\u0103un G.","year":"1994","journal-title":"Bulletin of the EATCS"},{"unstructured":"G.\u00a0P\u0103un, G.\u00a0Rozenberg and A.\u00a0Salomaa, DNA Computing: New Computing, Paradigms (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag, Berlin, Heidelberg, 2006. ISBN 3540641963.","key":"ref021"},{"doi-asserted-by":"publisher","key":"ref022","DOI":"10.1016\/S0019-9958(74)91049-3"},{"doi-asserted-by":"publisher","key":"ref023","DOI":"10.1016\/S0022-0000(74)80057-7"},{"doi-asserted-by":"publisher","key":"ref024","DOI":"10.1023\/B:NACO.0000006769.27984.23"},{"issue":"1","key":"ref025","first-page":"317","volume":"12","author":"Verlan S.","year":"2007","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"2","key":"ref026","first-page":"210","volume":"18","author":"Verlan S.","year":"2010","journal-title":"The Computer Science Journal of Moldova"},{"unstructured":"M.\u00a0Vu, On Insertion-Deletion Systems with Substitution Rules, Master\u2019s thesis, Informatikwissenschaften, Universit\u00e4t Trier, Germany, 2019.","key":"ref027"},{"doi-asserted-by":"crossref","unstructured":"M.\u00a0Vu and H.\u00a0Fernau, Insertion-deletion systems with substitutions I, in: Beyond the Horizon of Computability \u2013 16th Conference on Computability in Europe, CiE, M.\u00a0Anselmo, G.D.\u00a0Vedova, F.\u00a0Manea and A.\u00a0Pauly, eds, Lecture Notes in Computer Science, Vol.\u00a012098, Springer, 2020, pp.\u00a0366\u2013378.","key":"ref028","DOI":"10.1007\/978-3-030-51466-2_33"},{"doi-asserted-by":"publisher","key":"ref029","DOI":"10.1007\/978-3-030-62536-8_19"},{"doi-asserted-by":"publisher","key":"ref030","DOI":"10.1007\/978-3-030-67731-2_42"},{"doi-asserted-by":"publisher","key":"ref031","DOI":"10.1145\/321796.321811"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210345","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-210345","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210345","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:13Z","timestamp":1757420533000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-210345"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,11]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,12]]}},"alternative-id":["10.3233\/COM-210345"],"URL":"https:\/\/doi.org\/10.3233\/com-210345","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"type":"print","value":"2211-3568"},{"type":"electronic","value":"2211-3576"}],"subject":[],"published":{"date-parts":[[2021,10,11]]}}}