nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Reversing Steps in Membrane Systems Computations

verfasst von : G. Michele Pinna

Erschienen in: Membrane Computing

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The issue of reversibility in computational paradigms has gained interest in recent years. In this paper we investigate how to reverse steps in membrane systems computations. The problem is that computation steps in membrane systems do not preserve all the information that has to be used when reversing them. We try to formalize the relevant information needed, and we show that the proposed approach enjoy the so called loop lemma, which basically assures that the undoing obtained by reversely applying rules is correct.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Tissue P Systems with Rule Production/Removal

Nächstes Kapitel Families of Languages Encoded by SN P Systems

This is testified by the series of workshops and conferences entitled Reversible Computation (RC) organized since 2009, which is a conference since 2013.

This requirement is reasonable when one imagine that reversing means undoing the effects of a rule, thus if a rule just serves to annihilate all the objects to be rewritten then one can imagine that such a rule can be always reversed, in any multiplicity.

Agrigoroaiei, O., Ciobanu, G.: Reversing computation in membrane systems. J. Logic Algebraic Program. 79(3–5), 278–288 (2010)MathSciNetCrossRefMATH

Agrigoroaiei, O., Ciobanu, G.: Rule-based and object-based event structures for membrane systems. J. Logic Algebraic Program. 79(6), 295–303 (2010)MathSciNetCrossRefMATH

Alhazov, A., Freund, R., Morita, K.: Sequential and maximally parallel multiset rewriting: reversibility and determinism. Nat. Comput. 11(1), 95–106 (2012)MathSciNetCrossRefMATH

Aman, B., Ciobanu, G.: Computational power of protein interaction networks. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol. 7956, pp. 248–249. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39074-6_25 CrossRef

Ciobanu, G., Pan, L., Păun, G., Pérez-Jiménez, M.J.: P systems with minimal parallelism. Theoret. Comput. Sci. 378(1), 117–130 (2007)MathSciNetCrossRefMATH

Ciobanu, G., Pinna, G.M.: Catalytic Petri nets are turing complete. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 192–203. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28332-1_17 CrossRef

Ciobanu, G., Pinna, G.M.: Catalytic and communicating Petri nets are Turing complete. Inf. Comput. 239, 55–70 (2014)MathSciNetCrossRefMATH

Danos, V., Krivine, J.: Reversible communicating systems. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 292–307. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28644-8_19 CrossRef

Freund, R., Kari, L., Oswald, M., Sosík, P.: Computationally universal P systems without priorities: two catalysts are sufficient. Theoret. Comput. Sci. 330(2), 251–266 (2005)MathSciNetCrossRefMATH

10.

Giachino, E., Lanese, I., Mezzina, C.A., Tiezzi, F.: Causal-consistent reversibility in a tuple-based language. In: Daneshtalab, M., Aldinucci, M., Leppänen, V., Lilius, J., Brorsson, M. (eds.) PDP 2015, pp. 467–475. IEEE Computer Society (2015)

11.

Ibarra, O.H.: On strong reversibility in P systems and related problems. Int. J. Found. Comput. Sci. 22(1), 7–14 (2011)MathSciNetCrossRefMATH

12.

Kleijn, J., Koutny, M.: A Petri net model for membrane systems with dynamic structure. Nat. Comput. 8(4), 781–796 (2009)MathSciNetCrossRefMATH

13.

Kleijn, J.H.C.M., Koutny, M., Rozenberg, G.: Towards a Petri net semantics for membrane systems. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol. 3850, pp. 292–309. Springer, Heidelberg (2006). https://doi.org/10.1007/11603047_20 CrossRef

14.

Lanese, I., Mezzina, C.A., Stefani, J.-B.: Reversing higher-order Pi. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 478–493. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15375-4_33 CrossRef

15.

Lanese, I., Mezzina, C.A., Stefani, J.: Reversibility in the higher-order \(\pi \)-calculus. Theoret. Comput. Sci. 625, 25–84 (2016)MathSciNetCrossRefMATH

16.

Lanese, I., Mezzina, C.A., Tiezzi, F.: Causal-consistent reversibility. Bull. EATCS (114) (2014)

17.

Leporati, A., Zandron, C., Mauri, G.: Reversible P systems to simulate Fredkin circuits. Fundamenta Informaticae 74(4), 529–548 (2006)MathSciNetMATH

18.

Nishida, T.Y.: Reversible P systems with symport/antiport rules. In: Paun, G., Pérez-Jiménez, M.J., Riscos-Núñez, A. (eds.) WMC 2010, pp. 452–460 (2010)

19.

Phillips, I., Ulidowski, I.: Reversibility and asymmetric conflict in event structures. J. Logic Algebraic Methods Program. 84(6), 781–805 (2015)MathSciNetCrossRefMATH

20.

Pinna, G.M., Saba, A.: Modeling dependencies and simultaneity in membrane system computations. Theoret. Comput. Sci. 431, 13–39 (2012)MathSciNetCrossRefMATH

21.

Păun, A., Păun, G.: The power of communication: P systems with Symport/Antiport. New Gener. Comput. 20(3), 295–306 (2002)CrossRefMATH

22.

Păun, G.: Computing with membranes: an introduction. Bull. EATCS 67, 139–152 (1999)MathSciNetMATH

23.

Păun, G., Rozenberg, G., Salomaa, A.: The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford (2010)CrossRefMATH

24.

Song, T., Shi, X., Xu, J.: Reversible spiking neural P systems. Front. Comput. Sci. 7(3), 350–358 (2013)MathSciNetCrossRef

Titel: Reversing Steps in Membrane Systems Computations
verfasst von: G. Michele Pinna
Verlag: Springer International Publishing
Buch: Membrane Computing
Print ISBN: 978-3-319-73358-6

Electronic ISBN: 978-3-319-73359-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-73359-3_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner