Abstract.
The generative capability of several variants of P systems with symport/antiport is studied via the simulation of counter automata. This leads to the reduction of the complexity, expressed in number of membranes and weight of rules, of P systems generating recursively enumerable sets.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Csuhaj-Varjú, E., Vaszil, G. (2002) P automata or purely communicating accepting P systems. In: Păun, G. et al. (eds.) Membrane computing: International workshop, pp. 219-233. Springer, Berlin Heidelberg New York
Freund, R., Oswald, M. (2002) P systems with activated/prohibited membrane channels. In: Păun, G. et al. (eds.) Membrane computing: International workshop, 261-269. Springer, Berlin Heidelberg New York
Freund, R., Oswald, M. (2002) A short note on analysing P systems with antiport rules. Bulletin of the European Association for Theoretical Computer Science 78: 231-236
Freund, R., Păun, A. (2002) Membrane systems with symport/antiport rules: Universality results. In: Păun, G. et al. (eds), Membrane computing: International workshop, pp. 270-287. Springer, Berlin Heidelberg New York
Freund, R., Păun, G. (2001) On the number of non-terminals in graph-controlled programmed, and matrix grammars. In: Margenstern, M., Rogozhin, Y. (eds.) Machines, computations, and universality: Third International Conference, pp. 214-225. Springer, Berlin Heidelberg New York
Frisco, P., Hoogeboom, H.J. (2002) Simulating counter automata by P systems with symport/antiport. In: Păun, G. et al. (eds.) Membrane computing: International workshop, pp. 288-301. Springer, Berlin Heidelberg New York
Hoogeboom, H.J. (2002) Carriers and counters. P-systems with carriers vs. (blind) counter automata. In: Ito, M., Toyama, M. (eds.) Developments in language theory. 6th International conference, DLT 2002. Kyoto, Japan, September 2002. Revised papers, vol. 2450 (Lecture Notes in Computer Science), pp. 140-151
Hopcroft, J.E., Ullman, D. (1979) Introduction to automata theory, languages, and computation. Addison-Wesley
Ionescu, M., Martín-Vide, C., Păun, A., Păun, G. (2002) Unexpected universality results for three classes of P systems with symport/antiport, vol. 2568 (Lecture Notes in Computer Science), pp. 281-290. Hokkaido University, Springer, Berlin Heidelberg New York
Margenstern, M., Rogozhin, Y. (eds.) (2001) Machines, computations, and universality: Third International Conference. MCU 2001 Chisinau, Moldavia, May 23-27, 2001, Proceedings, vol. 2055 (Lecture Notes in Computer Science). Springer, Berlin Heidelberg New York
Martín-Vide, C., Păun, A., Păun, G. (2002) Membrane computing: New results, new problems. Bulletin of the European Association for Theoretical Computer Science 78: 204-212
Martín-Vide, C., Păun, A., Păun, G. (2002) On the power of P systems with symport rules. The Journal of Universal Computer Science 8: 317-331
Martín-Vide, C., Păun, A., Păun, G., Rozenberg, G. (2002) Membrane systems with coupled transport: universality and normal forms. Fundamenta Informaticae 49: 1-15
Martín-Vide, C., Păun, G. (2001) Computing with membranes (P systems): Universality results. In: Margenstern, M., Rogozhin, Y. (eds.) Machines, computations, and universality: Third International Conference, pp. 82-101. Springer, Berlin Heidelberg New York
Minsky, M.L. (1961) Recursive unsolvability of Post’s problem of “tag” and other topics in theory of Turing machines. Annals of Mathematics 74(3): 437-455
Păun, A., Păun, G. (2002) The power of communication: P systems with symport/antiport. New Generation Computing 20(3): 295-306
Păun, G. (2000) Computing with membranes. Journal of Computer and System Sciences 1(61): 108-143
Păun, G. (2000) Computing with membranes (P systems): twenty six research topics. TR 140, CDMTCS, pp. 203-217. University of Auckland, New Zealand
Păun, G. (2002) Membrane computing. An introduction. Springer, Berlin Heidelberg New York
Păun, G., Rozenberg, G. (2002) A guide to membrane computing. Theoretical Computer Science 287: 73-100
Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) (2002) Membrane computing: International Workshop, WMC-CdeA 2002, Curtea de Arges, Romania, August 19-23, 2002. Revised Papers, vol. 2597 (Lecture Notes in Computer Science).
Sosík, P., Freund, R. (2002) P systems without priorities are computationally universal. In: Păun, G. et al. (eds.), Membrane computing: International Workshop, pp. 400-409. Springer, Berlin Heidelberg New York
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 4 December 2003, Published online: 3 November 2004
Rights and permissions
About this article
Cite this article
Frisco, P., Hoogeboom, H.J. P systems with symport/antiport simulating counter automata. Acta Informatica 41, 145–170 (2004). https://doi.org/10.1007/s00236-004-0154-y
Issue Date:
DOI: https://doi.org/10.1007/s00236-004-0154-y