Abstract
We introduce some restricted models of symport/antiport P systems that are used as acceptors (respectively, generators) of sets of tuples of non-negative integers and show that they characterize precisely the semilinear sets. Specifically, we prove that a set R ⊆ Nk is accepted (respectively, generated) by a restricted system if and only if R is a semilinear set. We also show that “slight” extensions of the models will allow them to accept (respectively, generate) non-semilinear sets. In fact, for these extensions, the emptiness problem is undecidable.
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
Csuhaj-Varjú, E., Ibarra, O.H., Vaszil, G.: On the computational complexity of P automata. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 76–89. Springer, Heidelberg (2005)
Csuhaj-Varjú, E., Martín-Vide, C., Mitrana, V.: Multiset automata. In: Calude, C.S., Pun, G., Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. LNCS, vol. 2235, pp. 69–84. Springer, Heidelberg (2001)
Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)
Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. Journal of the ACM 25, 116–133 (1978)
Ibarra, O.H.: On membrane hierarchy in P systems. Theoretical Computer Science 334, 115–129 (2005)
Ito, M., Martín-Vide, C., Păun, G.: A characterization of Parikh sets of ETOL languages in terms of P systems. In: Ito, M., Păun, G., Yu, S. (eds.) Words, Semigroups, and Transductions, pp. 239–253. World Scientific, Singapore (2001)
Minsky, M.: Recursive unsolvability of Post’s problem of Tag and other topics in the theory of Turing machines. Ann. of Math. 74, 437–455 (1961)
Martín-Vide, C., Păun, G., Pazos, J., Rodríguez-Patón, A.: Tissue P systems. Theoretical Computer Science 296, 295–326 (2003)
Păun, A., Păun, G.: The power of communication: P systems with symport/antiport. New Generation Computing 20(3), 295–306 (2002)
Păun, G.: Membrane Computing. An Introduction. Springer, Berlin (2002)
Păun, G., Pazos, J., Pérez-Jiménez, M., Rodríguez-Patón, A.: Symport/antiport P systems with three objects are universal. Fundamenta Informaticae 64(1-4), 353–367 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ibarra, O.H., Woodworth, S., Yen, HC., Dang, Z. (2006). On Symport/Antiport P Systems and Semilinear Sets. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2005. Lecture Notes in Computer Science, vol 3850. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11603047_18
Download citation
DOI: https://doi.org/10.1007/11603047_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30948-2
Online ISBN: 978-3-540-32340-2
eBook Packages: Computer ScienceComputer Science (R0)