{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:32:28Z","timestamp":1777645948255,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"1-4","license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p>It is known that insertion-deletion (P) systems with two symbols context-free insertion and deletion rules are not computationally complete. It is thus interesting to consider conditions that would allow such systems to reach computational completeness. In this paper we consider insertion-deletion P systems with insertion and deletion operations applied only at the ends of string (we call them exo-operations). We show that such systems with one-symbol insertion and deletion of up to two symbols are computationally complete, and so are systems with insertion of up to two symbols and one-symbol deletion. The question about the computational power of insertion-deletion P systems with one-symbol insertion and one-symbol deletion operations applied at the ends of string is open. However, the tissue P systems reach computationally completeness even in this case.<\/jats:p>","DOI":"10.3233\/fi-2011-525","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T23:43:11Z","timestamp":1575330191000},"page":"13-28","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["P Systems with Insertion and Deletion Exo-Operations"],"prefix":"10.1177","volume":"110","author":[{"given":"Artiom","family":"Alhazov","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 di Milano-Bicocca degli Studi, Viale Sarca 336, 20126 Milano, Italy. artiom@math.md"}]},{"given":"Alexander","family":"Krassovitskiy","sequence":"additional","affiliation":[{"name":"Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya 35, 43002 Tarragona, Spain. alexander.krassovitskiy@estudiants.urv.cat"}]},{"given":"Yurii","family":"Rogozhin","sequence":"additional","affiliation":[{"name":"Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, Chi\u015fin\u0103u MD-2028, Moldova. rogozhin@math.md"}]},{"given":"Sergey","family":"Verlan","sequence":"additional","affiliation":[{"name":"D\u00e9partement Informatique, Universit\u00e9 Paris Est, 61 av. G\u00e9n\u00e9ral de Gaulle, 94010 Cr\u00e9teil, France. verlan@univ-paris12.fr"}]}],"member":"179","published-online":{"date-parts":[[2011,1,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2011-525","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2011-525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:33:52Z","timestamp":1777444432000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2011-525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,1]]},"references-count":0,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.3233\/FI-2011-525"],"URL":"https:\/\/doi.org\/10.3233\/fi-2011-525","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,1]]}}}