nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Reversible Computation in Petri Nets

verfasst von : Anna Philippou, Kyriaki Psara

Erschienen in: Reversible Computation

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

Reversible computation is an unconventional form of computing where any executed sequence of operations can be executed in reverse at any point during computation. In this paper we propose a reversible approach to Petri nets by introducing machinery and associated operational semantics to tackle the challenges of the three main forms of reversibility, namely, backtracking, causal reversing and out-of-causal-order reversing. Our proposal concerns a variation of Petri nets where tokens are persistent and are distinguished from each other by an identity. Our design decisions are influenced by applications in biochemistry but the methodology can be applied to a wide range of problems that feature reversibility. We demonstrate the applicability of our approach with an example of a biochemical system and an example of a transaction-processing system both featuring reversible behaviour.

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 On Reversibility and Broadcast

Nächstes Kapitel Event Structure Semantics of (controlled) Reversible CCS

Altenkirch, T., Grattage, J.: A functional quantum programming language. In: Proceedings of LICS 2005, pp. 249–258 (2005)

Bacci, G., Danos, V., Kammar, O.: On the statistical thermodynamics of reversible communicating processes. In: Proceedings of CALCO 2011. LNCS, vol. 6859, pp. 1–18. Springer, Heidelberg (2011)

Barylska, K., Gogolinska, A., Mikulski, L., Philippou, A., Piatkowski, M., Psara, K.: Reversing computations modelled by coloured Petri nets. In: Proceedings of ATEAD 2018 (2018, to appear)

Barylska, K., Koutny, M., Mikulski, L., Piatkowski, M.: Reversible computation vs. reversibility in Petri nets. Sci. Comput. Program. 151, 48–60 (2018)CrossRef

Barylska, K., Mikulski, L., Piatkowski, M., Koutny, M., Erofeev, E.: Reversing transitions in bounded Petri nets. In: Proceedings of CS&P 2016, vol. 1698. CEUR Workshop Proceedings, pp. 74–85. CEUR-WS.org (2016)

Cardelli, L., Laneve, C.: Reversible structures. In: Proceedings of CMSB 2011, pp. 131–140. ACM (2011)

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_19CrossRef

Danos, V., Krivine, J.: Transactions in RCCS. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 398–412. Springer, Heidelberg (2005). https://doi.org/10.1007/11539452_31CrossRef

Danos, V., Krivine, J.: Formal molecular biology done in CCS-R. Electron. Notes Theor. Comput. Sci. 180(3), 31–49 (2007)CrossRef

10.

Gay, S.J., Nagarajan, R.: Communicating quantum processes. In: Proceedings of POPL 2005, pp. 145–157 (2005)

11.

Jensen, K., Kristensen, L.M.: Coloured Petri Nets - Modelling and Validation of Concurrent Systems. Springer, Heidelberg (2009)CrossRef

12.

Kuhn, S., Ulidowski, I.: A calculus for local reversibility. In: Devitt, S., Lanese, I. (eds.) RC 2016. LNCS, vol. 9720, pp. 20–35. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40578-0_2CrossRef

13.

Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5(3), 183–191 (1961)MathSciNetCrossRef

14.

Lanese, I., Lienhardt, M., Mezzina, C.A., Schmitt, A., Stefani, J.-B.: Concurrent flexible reversibility. In: Felleisen, M., Gardner, P. (eds.) ESOP 2013. LNCS, vol. 7792, pp. 370–390. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37036-6_21CrossRef

15.

Lanese, I., Mezzina, C.A., Schmitt, A., Stefani, J.-B.: Controlling reversibility in higher-order Pi. In: Katoen, J.-P., König, B. (eds.) CONCUR 2011. LNCS, vol. 6901, pp. 297–311. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23217-6_20CrossRef

16.

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

17.

Philippou, A., Psara, K.: Reversible computation in Petri nets. CoRR, arXiv:abs/1804.04607 (2018)

18.

Phillips, I., Ulidowski, I.: Reversing algebraic process calculi. In: Aceto, L., Ingólfsdóttir, A. (eds.) FoSSaCS 2006. LNCS, vol. 3921, pp. 246–260. Springer, Heidelberg (2006). https://doi.org/10.1007/11690634_17CrossRef

19.

Phillips, I., Ulidowski, I., Yuen, S.: A reversible process calculus and the modelling of the ERK signalling pathway. In: Glück, R., Yokoyama, T. (eds.) RC 2012. LNCS, vol. 7581, pp. 218–232. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36315-3_18CrossRefMATH

20.

Phillips, I., Ulidowski, I., Yuen, S.: Modelling of bonding with processes and events. In: Dueck, G.W., Miller, D.M. (eds.) RC 2013. LNCS, vol. 7948, pp. 141–154. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38986-3_12CrossRefMATH

21.

Ulidowski, I., Phillips, I., Yuen, S.: Concurrency and reversibility. In: Yamashita, S., Minato, S. (eds.) RC 2014. LNCS, vol. 8507, pp. 1–14. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08494-7_1CrossRef

22.

Glabbeek, R.J.: The individual and collective token interpretations of Petri nets. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 323–337. Springer, Heidelberg (2005). https://doi.org/10.1007/11539452_26CrossRef

23.

van Glabbeek, R.J., Goltz, U., Schicke, J.-W.: On causal semantics of Petri nets. In: Katoen, J.-P., König, B. (eds.) CONCUR 2011. LNCS, vol. 6901, pp. 43–59. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23217-6_4CrossRef

Titel: Reversible Computation in Petri Nets
verfasst von: Anna Philippou
Kyriaki Psara
Verlag: Springer International Publishing
Buch: Reversible Computation
Print ISBN: 978-3-319-99497-0

Electronic ISBN: 978-3-319-99498-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-99498-7_6

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"