Abstract
Reversible computation has attracted increasing interest in recent years, with applications in hardware, software and biochemistry. In this paper we show how to model reversibility in concurrent computation as realised abstractly in terms of event structures. Two different forms of event structures are presented and it is shown how to extend them with reversibility.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baldan, P., Corradini, A., Montanari, U.: Contextual Petri nets, asymmetric event structures, and processes. Information and Computation 171(1), 1–49 (2001)
Bednarczyk, M.A.: Hereditary history preserving bisimulations or what is the power of the future perfect in program logics. Technical Report ICS PAS, Polish Academy of Sciences (1991)
Berry, G., Boudol, G.: The chemical abstract machine. Theoretical Computer Science 96(1), 217–248 (1992)
Cardelli, L., Laneve, C.: Reversible structures. In: 9th International Conference on Computational Methods in Systems Biology, pp. 131–140. ACM (2011)
Cristescu, I., Krivine, J., Varacca, D.: A compositional semantics for the reversible p-calculus. In: Proceedings of LICS 2013, pp. 388–397. IEEE Computer Society (2013)
Danos, V., Krivine, J.: Reversible communicating systems. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 292–307. Springer, Heidelberg (2004)
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)
Danos, V., Krivine, J.: Formal molecular biology done in CCS-R. In: Proceedings of BioConcur 2003. ENTCS, vol. 180, pp. 31–49 (2007)
Giachino, E., Lanese, I., Mezzina, C.A.: Causal-consistent reversible debugging. In: Gnesi, S., Rensink, A. (eds.) FASE 2014 (ETAPS). LNCS, vol. 8411, pp. 370–384. Springer, Heidelberg (2014)
van Glabbeek, R.J., Goltz, U.: Refinement of actions and equivalence notions for concurrent systems. Acta Informatica 37, 229–327 (2001)
Hennessy, M., Milner, R.: Algebraic laws for non-determinism and concurrency. Journal of the ACM 32, 137–161 (1985)
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)
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)
Lanese, I., Mezzina, C.A., Stefani, J.-B.: Controlled reversibility and compensations. In: Glück, R., Yokoyama, T. (eds.) RC 2012. LNCS, vol. 7581, pp. 233–240. Springer, Heidelberg (2013)
Nielsen, M., Plotkin, G.D., Winskel, G.: Petri nets, event structures and domains, part I. Theoretical Computer Science 13, 85–108 (1981)
Phillips, I.C.C., 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)
Phillips, I.C.C., Ulidowski, I.: Reversing algebraic process calculi. Journal of Logic and Algebraic Programming 73, 70–96 (2007)
Phillips, I.C.C., Ulidowski, I.: A hierarchy of reverse bisimulations on stable configuration structures. Mathematical Structures in Computer Science 22, 333–372 (2012)
Phillips, I., Ulidowski, I.: Reversibility and asymmetric conflict in even structures. In: D’Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013. LNCS, vol. 8052, pp. 303–318. Springer, Heidelberg (2013)
Phillips, I.C.C., Ulidowski, I.: Event Identifier Logic. Mathematical Structures in Computer Science 24, 1–51 (2014)
Phillips, I.C.C., 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)
Phillips, I.C.C., 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)
van Glabbeek, R.J., Plotkin, G.D.: Configuration structures, event structures and Petri nets. Theoretical Computer Science 410(41), 4111–4159 (2009)
van Glabbeek, R.J., Plotkin, G.D.: Event structures for resolvable conflict. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 550–561. Springer, Heidelberg (2004)
Varacca, D., Yoshida, N.: Typed event structures and the linear π-calculus. Theoretical Computer Science 411(19), 1949–1973 (2010)
Winskel, G.: Event structures. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 255, pp. 325–392. Springer, Heidelberg (1987)
Winskel, G.: Events, causality and symmetry. Computer Journal 54(1), 42–57 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ulidowski, I., Phillips, I., Yuen, S. (2014). Concurrency and Reversibility. In: Yamashita, S., Minato, Si. (eds) Reversible Computation. RC 2014. Lecture Notes in Computer Science, vol 8507. Springer, Cham. https://doi.org/10.1007/978-3-319-08494-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-08494-7_1
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08493-0
Online ISBN: 978-3-319-08494-7
eBook Packages: Computer ScienceComputer Science (R0)