Abstract
In this article we consider insertion-deletion P systems inserting or deleting one symbol in one or two symbol(s) left context (more precisely of size (1,2,0;1,1,0) and (1,1,0;1,2,0)). We show that computational completeness can be achieved by using only 3 membranes in a tree-like structure. Hence we obtain a trade-off between the sizes of contexts of insertion and deletion rules and the number of membranes sufficient for computational completeness.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alhazov, A., Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Small size insertion and deletion systems. In: Martin-Vide, C. (ed.) Scientific Applications of Language Methods. Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory, vol. 2, ch. 9, pp. 459–524. World Sci. (2010)
Alhazov, A., Krassovitskiy, A., Rogozhin, Y., Verlan, S.: P Systems with Minimal Insertion and Deletion. Theoretical Computer Science 412(1-2), 136–144 (2011)
Benne, R.: RNA Editing: The Alteration of Protein Coding Sequences of RNA. Ellis Horwood, Chichester, West Sussex (1993)
Biegler, F., Burrell, M.J., Daley, M.: Regulated RNA rewriting: Modelling RNA editing with guided insertion. Theor. Comput. Sci. 387(2), 103–112 (2007)
Csuhaj-Varjú, E., Salomaa, A.: Networks of Parallel Language Processors. In: Păun, G., Salomaa, A. (eds.) NTFL. LNCS, vol. 1218, pp. 299–318. Springer, Heidelberg (1997)
Daley, M., Kari, L., Gloor, G., Siromoney, R.: Circular contextual insertions/deletions with applications to biomolecular computation. In: SPIRE/CRIWG, pp. 47–54 (1999)
Freund, R., Kogler, M., Rogozhin, Y., Verlan, S.: Graph-controlled insertion-deletion systems. In: McQuillan, I., Pighizzini, G. (eds.) Proc. of 12th Workshop on Descriptional Complexity of Formal Systems. EPTCS, vol. 31, pp. 88–98 (2010)
Galiukschov, B.: Semicontextual grammars. Matem. Logica i Matem. Lingvistika, 38–50, Tallin University (1981) (in Russian)
Geffert, V.: Normal forms for phrase-structure grammars. ITA 25, 473–498 (1991)
Haussler, D.: Insertion and Iterated Insertion as Operations on Formal Languages. PhD thesis, Univ. of Colorado at Boulder (1982)
Haussler, D.: Insertion languages. Information Sciences 31(1), 77–89 (1983)
Kari, L.: On Insertion and Deletion in Formal Languages. PhD thesis, University of Turku (1991)
Kari, L., Păun, G., Thierrin, G., Yu, S.: At the crossroads of DNA computing and formal languages: Characterizing RE using insertion-deletion systems. In: Proc. of 3rd DIMACS Workshop on DNA Based Computing, Philadelphia, pp. 318–333 (1997)
Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C., McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956)
Krassovitskiy, A.: Complexity and Modeling Power of Insertion-Deletion Systems. PhD thesis, Universitat Rovira i Virgili, Tarragona, Spain (2011)
Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Further results on insertion-deletion systems with one-sided contexts. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 333–344. Springer, Heidelberg (2008)
Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Computational power of P systems with small size insertion and deletion rules. In: Neary, T., Woods, D., Seda, A.K., Murphy, N. (eds.) Proc. International Workshop on The Complexity of Simple Programs, Cork, Ireland, December 6-7. EPTCS, vol. 1, pp. 108–117 (2009)
Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Computational power of insertion-deletion (P) systems with rules of size two. Natural Computing 10(2), 835–852 (2011)
Marcus, S.: Contextual grammars. Rev. Roum. Math. Pures Appl. 14, 1525–1534 (1969)
Margenstern, M., Păun, G., Rogozhin, Y., Verlan, S.: Context-free insertion-deletion systems. Theor. Comput. Sci. 330(2), 339–348 (2005)
Matveevici, A., Rogozhin, Y., Verlan, S.: Insertion-deletion systems with one-sided contexts. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 205–217. Springer, Heidelberg (2007)
Păun, G.: Marcus Contextual Grammars. Kluwer Academic Publishers, Norwell (1997)
Păun, G.: Membrane Computing. An Introduction. Springer (2002)
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer (1998)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer, Berlin (1997)
Smith, W.D.: DNA computers in vitro and in vivo. In: Lipton, R., Baum, E. (eds.) Proceedings of DIMACS Workshop on DNA Based Computers. DIMACS Series in Discrete Math. and Theoretical Computer Science, pp. 121–185. Amer. Math. Society (1996)
Takahara, A., Yokomori, T.: On the computational power of insertion-deletion systems. In: Hagiya, M., Ohuchi, A. (eds.) DNA8. LNCS, vol. 2568, pp. 269–280. Springer, Heidelberg (2003)
Verlan, S.: On minimal context-free insertion-deletion systems. Journal of Automata, Languages and Combinatorics 12(1-2), 317–328 (2007)
Verlan, S.: Study of language-theoretic computational paradigms inspired by biology. Habilitation thesis, University of Paris Est (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ivanov, S., Verlan, S. (2014). About One-Sided One-Symbol Insertion-Deletion P Systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. CMC 2013. Lecture Notes in Computer Science, vol 8340. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54239-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-54239-8_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54238-1
Online ISBN: 978-3-642-54239-8
eBook Packages: Computer ScienceComputer Science (R0)