Abstract
Membrane computing is a formal framework of distributed parallel computing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for reversible P systems with either priorities or inhibitors, and a negative conjecture is stated for reversible P systems without such control. Strongly reversible P systems without control have shown to only generate sub-finite sets of numbers; this limitation does not hold if inhibitors are used.
Another concept considered is strong determinism, which is a syntactic property, as opposed to the determinism typically considered in membrane computing. Strongly deterministic P systems without control only accept sub-regular sets of numbers, while systems with promoters and inhibitors are universal.
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
Agrigoroaiei, O., Ciobanu, G.: Dual P Systems. In: Corne, D.W., Frisco, P., Paun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2008. LNCS, vol. 5391, pp. 95–107. Springer, Heidelberg (2009)
Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and Development 17, 525–532 (1973)
Calude, C., Păun, Gh.: Bio-steps beyond Turing. BioSystems 77, 175–194 (2004)
Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theoret. Phys. 21, 219–253 (1982)
Ibarra, O.H.: On strong reversibility in P systems and related problems (manuscript)
Leporati, A., Zandron, C., Mauri, G.: Reversible P systems to simulate Fredkin circuits. Fundam. Inform. 74(4), 529–548 (2006)
Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
Morita, K.: Universality of a reversible two-counter machine. Theoret. Comput. Sci. 168, 303–320 (1996)
Morita, K.: A simple reversible logic element and cellular automata for reversible computing. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol. 2055, pp. 102–113. Springer, Heidelberg (2001)
Morita, K.: Simple universal one-dimensional reversible cellular automata. J. Cellular Automata 2, 159–165 (2007)
Morita, K., Nishihara, N., Yamamoto, Y., Zhang, Zh.: A hierarchy of uniquely parsable grammar classes and deterministic acceptors. Acta Inf. 34(5), 389–410 (1997)
Morita, K., Yamaguchi, Y.: A universal reversible Turing machine. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 90–98. Springer, Heidelberg (2007)
Păun, G.: Membrane Computing. An Introduction. Springer, Berlin (2002)
P systems webpage, http://ppage.psystems.eu/
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., Morita, K. (2010). On Reversibility and Determinism in P Systems. In: Păun, G., Pérez-Jiménez, M.J., Riscos-Núñez, A., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2009. Lecture Notes in Computer Science, vol 5957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11467-0_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-11467-0_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11466-3
Online ISBN: 978-3-642-11467-0
eBook Packages: Computer ScienceComputer Science (R0)