Abstract
In this article we present a universal splicing P system with 6 rules. Thus we improve the previous result that used 8 rules and lower the possible value for the boundary between the universality and non-universality for such systems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alhazov, A., Verlan, S.: Minimization strategies for maximally parallel multiset rewriting systems. Technical Report 862, TUCS Report No. 862 (2008), http://tucs.fi and arXiv:1009.2706v1 [cs.FL] (September 14, 2010), http://arxiv.org/abs/1009.2706
Cocke, J., Minsky, M.: Universality of Tag Systems with P=2. Journal of the ACM 11(1), 15–20 (1964)
Csuhaj-Varjú, E., Margenstern, M., Vaszil, G., Verlan, S.: Small Computationally Complete Symport/Antiport P systems. Theoretical Computer Science 372(2-3), 152–164 (2007)
Frisco, P.: Computing with Cells: Advances in Membrane Computing. Oxford University Press, Oxford (2009)
Head, T.: Formal Language Theory and DNA: an Analysis of the Generative Capacity of Specific Recombinant Behaviors. Bulletin of Mathematical Biology 49(6), 737–759 (1987)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (2001)
Minsky, M.: Computations: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
Păun, G.: Membrane Computing. An Introduction. Springer, Heidelberg (2002)
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Heidelberg (1998)
Păun, G., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford (2010)
Rogozhin, Y., Verlan, S.: On the Rule Complexity of Universal Tissue P Systems. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol. 3850, pp. 356–362. Springer, Heidelberg (2006)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 3. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alhazov, A., Rogozhin, Y., Verlan, S. (2010). A Small Universal Splicing P System. In: Gheorghe, M., Hinze, T., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. CMC 2010. Lecture Notes in Computer Science, vol 6501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18123-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-18123-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18122-1
Online ISBN: 978-3-642-18123-8
eBook Packages: Computer ScienceComputer Science (R0)