On the Power of Small Size Insertion P Systems
Keywords:
P systems, insertion-deletion systems, context-free languages, matrix grammars, computational completenessAbstract
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.References
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.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
