On the Power of Small Size Insertion P Systems


  • Alexander Krassovitskiy University Rovira i Virgili Research Group on Mathematical Linguistics Av. Catalunya, 35, Tarragona 43002, Spain


P systems, insertion-deletion systems, context-free languages, matrix grammars, computational completeness


In this article we investigate insertion systems of small size in the framework of P systems. We consider P systems with insertion rules having one symbol context and we show that they have the computational power of context-free matrix grammars. If contexts of length two are permitted, then any recursively enumerable language can be generated. In both cases a squeezing mechanism, an inverse morphism, and a weak coding are applied to the output of the corresponding P systems. We also show that if no membranes are used then corresponding family is equal to the family of context-free languages.


M. Daley, L. Kari, G. Gloor, R. Siromoney, Circular Contextual Insertions/Deletions with Applications to Biomolecular Computation, In: Proc. SPIRE'99 , pp. 47-54, 1999. http://dx.doi.org/10.1109/spire.1999.796577

L. Kari, From Micro-soft to Bio-soft: Computing with DNA, In:Proc. of Biocomputing and Emergent Computations, 146-164, 1997.

L. Kari, Gh. Păun, G. Thierrin, S. Yu, At the Crossroads of DNA Computing and Formal Languages: Characterizing RE Using Insertion-Deletion Systems. In: Proc. of 3rd DIMACS, pp. 318-333, 1997.

L. Kari, P. Sosík, On the Weight of Universal Insertion Grammars, TCS, 396(1-3), pp. 264-270, 2008. http://dx.doi.org/10.1016/j.tcs.2008.01.037

L. Kari, G. Thierrin, Contextual Insertion/Deletion and Computability, Information and Computation, 131, 1, pp. 47-61, 1996. http://dx.doi.org/10.1006/inco.1996.0091

A. Krassovitskiy, Yu. Rogozhin, S. Verlan, Further Results on Insertion-Deletion Systems with One-Sided Contexts, In Proc. of 2nd LATA08, LNCS, 5196, pp. 333-344, 2008.

A. Krassovitskiy, Yu. Rogozhin, S. Verlan, One-Sided Insertion and Deletion: Traditional and P Systems Case, CBM08, pp. 53-64, 2008.

A. Krassovitskiy, Yu. Rogozhin, S. Verlan, Computational Power of P Systems with Small Size Insertion and Deletion Rules, In:Proc of CSP08, pp. 137-148, 2008.

S. Marcus, Contextual Grammars, Rev. Roum. Math. Pures Appl., 14, pp 1525-1534, 1969. http://dx.doi.org/10.3115/990403.990451

M. Margenstern, Gh. Păun, Yu. Rogozhin, S. Verlan, Context-Free Insertion-Deletion Systems, TCS, 330, pp. 339-348, 2005. http://dx.doi.org/10.1016/j.tcs.2004.06.031

C. Martin-Vide, Gh. Păun, A. Salomaa, Characterizations of Recursively Enumerable Languages by Means of Insertion Grammars, TCS, 205, 1-2, pp. 195-205, 1998.

A. Matveevici, Yu. Rogozhin, S. Verlan, Insertion-Deletion Systems with One-Sided Contexts, LNCS, 4664, pp. 205-217, 2007. http://dx.doi.org/10.1007/978-3-540-74593-8_18

M. Mutyam, K. Krithivasan, A. S. Reddy, On Characterizing Recursively Enumerable Languages by Insertion Grammars, Fundamenta Informaticae, 64(1-4), pp. 317-324, 2005.

K. Onodera, New Morphic Characterization of Languages in Chomsky Hierarchy Using Insertion and Locality, In Proc. of 3rd LATA09, LNCS, 5457, pp. 648-659, 2009.

Gh. Păun, Computing with Membranes, Journal of Computer and System Sciences, Vol. 61, 1, pp. 108-143, 2000. http://dx.doi.org/10.1006/jcss.1999.1693

Gh. Păun, Marcus Contextual Grammars, Kluwer, Dordrecht, 1997. http://dx.doi.org/10.1007/978-94-015-8969-7

Gh. Păun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 163, pp. 226- 230, 2002. http://dx.doi.org/10.1007/978-3-642-56196-2

Gh. Păun, M. J. Pérez-Jiménez, T. Yokomori, Representations and Characterizations of Languages in Chomsky Hierarchy by Means of Insertion-Deletion Systems, International Journal of Foundations of Computer Science, 19, 4, pp. 859-871, 2008. http://dx.doi.org/10.1142/S0129054108006005

Gh. Păun, G. Rozenberg, A. Salomaa, DNA Computing. New Computing Paradigms, Springer-Verlag, Berlin, 1998.

G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, Springer-Verlag, Berlin, 1997.

A. Takahara, T. Yokomori, On the Computational Power of Insertion-Deletion Systems, DNA 2002, Sapporo, LNCS, 2568, pp. 269-280, 2003.

S. Verlan, On Minimal Context-Free Insertion-Deletion Systems, Journal of Automata, Languages and Combinatorics, 12, 1/2, pp. 317-328, 2007.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.