Abstract
Rewriting systems over adhesive categories have been recently introduced as a general framework which encompasses several rewriting-based computational formalisms, including various modelling frameworks for concurrent and distributed systems. Here we begin the development of a truly concurrent semantics for adhesive rewriting systems by defining the fundamental notion of process, well-known from Petri nets and graph grammars. The main result of the paper shows that processes capture the notion of true concurrency—there is a one-to-one correspondence between concurrent derivations, where the sequential order of independent steps is immaterial, and (isomorphism classes of) processes. We see this contribution as a step towards a general theory of true concurrency which specialises to the various concrete constructions found in the literature.
Partially supported by EPSRC grant GR/T22049/01, DFG project SANDS, EC RTN 2-2001-00346 SegraVis, MIUR project PRIN 2005015824 ART and EU IST-2004-16004 SEnSOria.
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.: Modelling Concurrent Computations: from Contextual Petri Nets to Graph Grammars. PhD thesis, Dipartimento di Informatica, Università di Pisa (2000)
Baldan, P., Corradini, A., König, B.: A static analysis technique for graph transformation systems. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154, pp. 381–395. Springer, Heidelberg (2001)
Baldan, P., Corradini, A., König, B.: Verifying finite-state graph grammars: an unfolding-based approach. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 83–98. Springer, Heidelberg (2004)
Baldan, P., Corradini, A., Montanari, U.: Concatenable graph processes: relating processes and derivation traces. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, Springer, Heidelberg (1998)
Baldan, P., Corradini, A., Montanari, U.: Unfolding and Event Structure Semantics for Graph Grammars. In: Thomas, W. (ed.) ETAPS 1999 and FOSSACS 1999. LNCS, vol. 1578, pp. 73–89. Springer, Heidelberg (1999)
Corradini, A., Montanari, U., Rossi, F.: Graph processes. Fundamenta Informaticae 26, 241–265 (1996)
Ehrig, H.: Introduction to the Algebraic Theory of Graph Grammars. In: Graph Grammars 1978. LNCS, vol. 73, pp. 1–69. Springer, Heidelberg (1979)
Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, F.: Parallelism and concurrency in high-level replacement systems. Mathematical Structures in Computer Science 1, 361–404 (1991)
Ehrig, H., Habel, A., Padberg, J., Prange, U.: Adhesive high-level replacement categories and systems. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 144–160. Springer, Heidelberg (2004)
Esparza, J., Römer, S., Vogler, W.: An improvement of McMillan’s unfolding algorithm. Formal Methods in System Design 20(20), 285–310 (2002)
Goltz, U., Reisig, W.: The non-sequential behaviour of Petri nets. Information and Control 57, 125–147 (1983)
Habel, A., Müller, J., Plump, D.: Double-pushout graph transformation revisited. Mathematical Structures in Computer Science 11(5), 637–688 (2001)
Lack, S., Sobociński, P.: Adhesive and quasiadhesive categories. Theoretical Informatics and Applications 39(2), 511–546 (2005)
McMillan, K.L.: Symbolic Model Checking. Kluwer, Dordrecht (1993)
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
Baldan, P., Corradini, A., Heindel, T., König, B., Sobociński, P. (2006). Processes for Adhesive Rewriting Systems. In: Aceto, L., Ingólfsdóttir, A. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2006. Lecture Notes in Computer Science, vol 3921. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11690634_14
Download citation
DOI: https://doi.org/10.1007/11690634_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33045-5
Online ISBN: 978-3-540-33046-2
eBook Packages: Computer ScienceComputer Science (R0)