{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:57:21Z","timestamp":1760234241076,"version":"build-2065373602"},"reference-count":34,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T00:00:00Z","timestamp":1619049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Insertion-deletion systems have been introduced as a formalism to model operations that find their counterparts in ideas of bio-computing, more specifically, when using DNA or RNA strings and biological mechanisms that work on these strings. So-called matrix control has been introduced to insertion-deletion systems in order to enable writing short program fragments. We discuss substitutions as a further type of operation, added to matrix insertion-deletion systems. For such systems, we additionally discuss the effect of appearance checking. This way, we obtain new characterizations of the family of context-sensitive and the family of recursively enumerable languages. Not much context is needed for systems with appearance checking to reach computational completeness. This also suggests that bio-computers may run rather traditionally written programs, as our simulations also show how Turing machines, like any other computational device, can be simulated by certain matrix insertion-deletion-substitution systems.<\/jats:p>","DOI":"10.3390\/a14050131","type":"journal-article","created":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T13:59:14Z","timestamp":1619099954000},"page":"131","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Adding Matrix Control: Insertion-Deletion Systems with Substitutions III"],"prefix":"10.3390","volume":"14","author":[{"given":"Martin","family":"Vu","sequence":"first","affiliation":[{"name":"Fachbereich 3, Universit\u00e4t Bremen, 28359 Bremen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4444-3220","authenticated-orcid":false,"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[{"name":"Fachbereich 4, Universit\u00e4t Trier, 54296 Trier, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,22]]},"reference":[{"key":"ref_1","unstructured":"Kari, L. (1991). On Insertions and Deletions in Formal Languages. [Ph.D. Thesis, University of Turku]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1090\/dimacs\/048\/23","article-title":"At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems","volume":"Volume 48","author":"Kari","year":"1999","journal-title":"DNA Based Computers III"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/cmb.1995.2.1","article-title":"Computing with DNA","volume":"2","author":"Beaver","year":"1995","journal-title":"J. Comput. Biol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF03024425","article-title":"DNA computing: Arrival of biological mathematics","volume":"19","author":"Kari","year":"1997","journal-title":"Math. Intell."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s11047-013-9396-3","article-title":"Generating and accepting P systems with minimal left and right insertion and deletion","volume":"13","author":"Freund","year":"2014","journal-title":"Nat. Comput."},{"key":"ref_6","unstructured":"Anselmo, M., Vedova, G.D., Manea, F., and Pauly, A. (2020). Insertion-Deletion Systems With Substitutions I. Computability in Europe, CiE, Springer Nature Switzerland AG."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/978-3-030-62536-8_19","article-title":"Insertion-Deletion Systems With Substitutions II","volume":"Volume 12442","author":"Jiraskova","year":"2020","journal-title":"Proceedings of the Descriptional Complexity of Formal Systems\u201422nd International Conference, DCFS"},{"key":"ref_8","unstructured":"Vu, M. (2019). On Insertion-Deletion Systems with Substitution Rules. [Master\u2019s Thesis, Informatikwissenschaften, Universit\u00e4t Trier]."},{"key":"ref_9","unstructured":"Kuppusamy, L., Mahendran, A., and Krishna, S.N. (2011, January 28\u201330). On Representing Natural Languages and Bio-molecular Structures using Matrix Insertion-deletion Systems and its Computational Completeness. Proceedings of the 1st International Workshop on AI Methods for Interdisciplinary Research in Language and Biology (ICAART 2011), Rome, Italy."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.tcs.2012.07.002","article-title":"Matrix insertion-deletion systems","volume":"456","author":"Petre","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","first-page":"61","article-title":"Some questions of phrase-structure grammars, I","volume":"4","year":"1965","journal-title":"Comput. Linguist."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Dassow, J., and P\u0103un, G. (1989). Regulated Rewriting in Formal Language Theory, EATCS Monographs in Theoretical Computer Science; Springer-Verlag.","DOI":"10.1007\/978-3-642-74932-2"},{"key":"ref_13","unstructured":"Martin-Vide, C. (2010). Small size insertion and deletion systems. Applications of Language Methods, Imperial College Press."},{"key":"ref_14","first-page":"210","article-title":"Recent Developments on Insertion-Deletion Systems","volume":"18","author":"Verlan","year":"2010","journal-title":"Comput. Sci. J. Mold."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/978-3-642-19056-8_23","article-title":"Matrix Insertion-Deletion Systems for Bio-Molecular Structures","volume":"Volume 6536","author":"Natarajan","year":"2011","journal-title":"Proceedings of the Distributed Computing and Internet Technology\u20147th International Conference"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s11047-017-9656-8","article-title":"Investigations on the power of matrix insertion-deletion systems with small sizes","volume":"17","author":"Fernau","year":"2018","journal-title":"Nat. Comput."},{"key":"ref_17","first-page":"192","article-title":"On Matrix Ins-Del Systems of Small Sum-Norm","volume":"Volume 11376","author":"Catania","year":"2019","journal-title":"SOFSEM: Theory and Practice of Computer Science"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1007\/s11047-010-9208-y","article-title":"Computational power of insertion-deletion (P) systems with rules of size two","volume":"10","author":"Krassovitskiy","year":"2011","journal-title":"Nat. Comput."},{"key":"ref_19","first-page":"317","article-title":"On Minimal Context-Free Insertion-Deletion Systems","volume":"12","author":"Verlan","year":"2007","journal-title":"J. Autom. Lang. Comb."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/BF01178731","article-title":"Petri net algorithms in the theory of matrix grammars","volume":"31","author":"Hauschildt","year":"1994","journal-title":"Acta Inform."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0019-9958(74)91049-3","article-title":"One-sided and two-sided context in formal grammars","volume":"25","author":"Penttonen","year":"1974","journal-title":"Inf. Control (Now Inf. Comput.)"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.tcs.2010.08.025","article-title":"P systems with minimal insertion and deletion","volume":"412","author":"Alhazov","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1006\/jcss.1999.1693","article-title":"Computing with Membranes","volume":"61","year":"2000","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-540-74593-8_18","article-title":"Insertion-Deletion Systems with One-Sided Contexts","volume":"Volume 4664","author":"Margenstern","year":"2007","journal-title":"Proceedings of the Machines Computations, and Universality, 5th International Conference"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-030-23247-4_8","article-title":"Descriptional Complexity of Matrix Simple Semi-conditional Grammars","volume":"Volume 11612","author":"Konstantinidis","year":"2019","journal-title":"Proceedings of the Descriptional Complexity of Formal Systems\u201421st IFIP WG 1.02 International Conference, DCFS"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Fernau, H., Kuppusamy, L., Oladele, R.O., and Raman, I. (2021). Improved descriptional complexity results on generalized forbidding grammars. Discret. Appl. Math.","DOI":"10.1016\/j.dam.2020.12.027"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1080\/00207169008803908","article-title":"Generalized forbidding grammars","volume":"36","author":"Meduna","year":"1990","journal-title":"Int. J. Comput. Math."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(85)90056-8","article-title":"A variant of random context grammars: Semi-conditional grammars","volume":"41","year":"1985","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","unstructured":"Van der Walt, P.J. (1972). Random context languages. Processing IFIP Congress, North-Holland Publishing Company."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/978-3-319-92435-9_7","article-title":"Computational Completeness of Simple Semi-conditional Insertion-Deletion Systems","volume":"Volume 10867","author":"Stepney","year":"2018","journal-title":"Unconventional Computation and Natural Computation, UCNC"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"127","DOI":"10.3233\/FI-2015-1203","article-title":"Random Context and Semi-conditional Insertion-deletion Systems","volume":"138","author":"Ivanov","year":"2015","journal-title":"Fundam. Inform."},{"key":"ref_32","first-page":"491","article-title":"On ordered variants of some regulated grammars","volume":"21","author":"Dassow","year":"1985","journal-title":"J. Inf. Process. Cybern. EIK"},{"key":"ref_33","first-page":"159","article-title":"Closure properties of ordered languages","volume":"58","author":"Fernau","year":"1996","journal-title":"EATCS Bull."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-030-23247-4_1","article-title":"A General Framework for Sequential Grammars with Control Mechanisms","volume":"Volume 11612","author":"Konstantinidis","year":"2019","journal-title":"Proceedings of the Descriptional Complexity of Formal Systems\u201421st International Conference DCFS"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/131\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:51:15Z","timestamp":1760161875000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,22]]},"references-count":34,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5]]}},"alternative-id":["a14050131"],"URL":"https:\/\/doi.org\/10.3390\/a14050131","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,4,22]]}}}