P Systems with Insertion and Deletion Exo-Operations

• Autorzy: Alhazov A. , Krassovitskiy A. , Rogozhin Y. , Verlan S.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

P systems with insertion-deletion operations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 13--28
• Opis fizyczny: Bibliogr. 27 poz., wykr.

Twórcy

autor

Alhazov A.

autor

Krassovitskiy A.

autor

Rogozhin Y.

autor

Verlan S.

• Institute ofMathematics and Computer Science, Academy of Sciences ofMoldova, Academiei 5, Chisinau MD-2028, Moldova,

Bibliografia

• [1] A. Alhazov, A. Krassovitskiy, Yu. Rogozhin, S. Verlan: P Systems with Minimal Insertion and Deletion. In: R. Gutiérrez-Escudero et. al.: RGNC report 1/2009, University of Seville, Seventh Brainstorming Week on Membrane Computing, vol. I, Fénix Editora, Sevilla (2009) 9-21.
• [2] A. Alhazov, A. Krassovitskiy, Yu. Rogozhin, S. Verlan: P Systems with Minimal Insertion and Deletion. Theoretical Computer Science 412, Elsevier (2011) 136-144.
• [3] R. Beene: RNA-editing: The Alteration of Protein Coding Sequences of RNA. In A.J. Turner (ed) Ellis Horwood Series in Molecular Biology, Chichester,West Sussex (1993).
• [4] M. Daley, L. Kari, G. Gloor, R. Siromoney: Circular Contextual Insertions/Deletions with Applications to Biomolecular Computation. In Proceedings of 6th Int. Symp. on String Processing and Information Retrieval, SPIRE'99, Mexico (1999) 47-54.
• [5] R. Freund, M. Kogler, Yu. Rogozhin, S. Verlan: Graph-Controlled Insertion-Deletion Systems. EPTCS 31 (2010) 88 - 98. DOI 10.4204/EPTCS.31.11
• [6] B.S. Galiukschov: Semicontextual Grammars. Matematika Logica i Matematika Linguistika, Tallin University (1981) 38-50 (in Russian).
• [7] L. Kari: On Insertion and Deletion in Formal Languages, PhD thesis, Univ. of Turku (1991).
• [8] L. Kari, Gh. Pǎun, G. Thierrin, S. Yu S: At the crossroads of DNA computing and formal languages: characterizing RE using insertion-deletion systems. In: Proceedings of 3rd DIMACS workshop on DNA based computing, Philadelphia (1997) 318-333.
• [9] L. Kari, G. Thierrin: Contextual Insertion/Deletion and Computability. Information and Computation 131(1) (1996) 47-61.
• [10] A. Krassovitskiy, Yu. Rogozhin, S. Verlan: Further results on insertion-deletion systems with one-sided contexts. In: C.Martin-Vide et. al. (eds) LATA 2008. 2nd Int. Conference on Language and Automata Theory and Applications, Tarragona, 2008. LNCS 5196, Springer (2008) 333-344.
• [11] A. Krassovitskiy, Yu. Rogozhin, S. Verlan: One-sided insertion and deletion: Traditional and P systems case. In: Proceedings of CBM'08, Int. Workshop on Computing with Biomolecules, Vienna (2008) 53-64.
• [12] A. Krassovitskiy, Yu. Rogozhin, S. Verlan: Computational Power of P Systems with Small Size Insertion and Deletion Rules. In: Proceedings of CSP'08, Int.Workshop on the Complexity of Simple Programs, University of Cork, Ireland (2008) 137-148.
• [13] A. Krassovitskiy, Yu. Rogozhin, S. Verlan: Computational Power of Insertion-Deletion (P) Systems with Rules of Size Two. Natural Computing, Springer (2010). DOI 10.1007/s11047-010-9208-y
• [14] A. Krassovitskiy: On the Power of Insertion P systems of Small Size. In: R. Gutiérrez-Escudero et. al.: RGNC report 1/2009, University of Seville, Seventh Brainstorming Week on Membrane Computing, vol. II, Fénix Editora, Sevilla (2009) 29-44.
• [15] M. Kudlek, Yu. Rogozhin: Small Universal Circular Post Machines. Computer Science Journal of Moldova 9(1) (2001) 34-52.
• [16] S. Marcus: Contextual grammars. Rev. Roum. Math. Pures. Appl. 14 (1969) 1525-1534.
• [17] M. Margenstern, Gh. Pǎun, Yu. Rogozhin, S. Verlan: Context-free insertion-deletion systems. Theoretical Computer Science 330(2) (2005) 339-348.
• [18] C. Martin-Vide, Gh. Pǎun, A. Salomaa: Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars. Theoretical Computer Science 205, 1/2 (1998) 195-205
• [19] A. Matveevici, Yu. Rogozhin, S. Verlan Insertion-Deletion Systems with One-Sided Contexts. LNCS 4664, Springer (2007) 205-217.
• [20] Gh. Pǎun: Marcus Contextual Grammars. Studies in Linguistics and Philosophy, Kluwer Academic Publishers, Dordrecht (1997).
• [21] Gh. Pǎun: Membrane Computing. An Introduction. Springer (2002).
• [22] Gh. Pǎun, G. Rozenberg, A. Salomaa: DNA computing. New computing paradigms. Springer-Verlag, Berlin (1998).
• [23] G. Rozenberg, A. Salomaa (eds): Handbook of Formal Languages. Springer, Berlin (1997).
• [24] W. Smith: DNA computers in Vitro and in Vivo. In: R.J. Lipton, E.B. Baum (eds): Proceedings of a DIMACS workshop, American Mathematical Society, Providence (1996) 121-185.
• [25] A. Takahara, T. Yokomori: On the Computational Power of Insertion-Deletion Systems. In: Proceedings of 8th Int. Workshop on DNA-based Computers, DNA8, Sapporo, 2002. Revised papers. LNCS 2568 (2003) 269-280.
• [26] S. Verlan: On Minimal Context-Free Insertion-Deletion Systems. Journal of Automata, Languages and Combinatorics 12 (1/2) (2007) 317-328.
• [27] P systems webpage. http://ppage.psystems.eu