A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting

F. Gadducci, R. Heckel, M. Llabrés, in: Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK), Elsevier, 1999, pp. 80–100.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
; ;
Abstract
In this paper the concurrent semantics of double-pushout (DPO) graph rewriting, which is classically defined in terms of shift-equivalence classes of graph derivations, is axiomatised via the construction of a free monoidal bi-category. In contrast to a previous attempt based on 2-categories, the use of bi-categories allows to define rewriting on concrete graphs. Thus, the problem of composition of isomorphism classes of rewriting sequences is avoided. Moreover, as a first step towards the recovery of the full expressive power of the formalism via a purely algebraic description, the concept of disconnected rules is introduced, i.e., rules whose interface graphs are made of disconnected nodes and edges only. It is proved that, under reasonable assumptions, rewriting via disconnected rules enjoys similar concurrency properties like in the classical approach.
Publishing Year
Proceedings Title
Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK)
Volume
29
Page
80-100
LibreCat-ID

Cite this

Gadducci F, Heckel R, Llabrés M. A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting. In: Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK). Vol 29. Electronic Notes in Theoretical Computer Science. Elsevier; 1999:80-100. doi:http://dx.doi.org/10.1016/S1571-0661(05)80309-3
Gadducci, F., Heckel, R., & Llabrés, M. (1999). A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting. In Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK) (Vol. 29, pp. 80–100). Elsevier. http://dx.doi.org/10.1016/S1571-0661(05)80309-3
@inproceedings{Gadducci_Heckel_Llabrés_1999, series={Electronic Notes in Theoretical Computer Science}, title={A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting}, volume={29}, DOI={http://dx.doi.org/10.1016/S1571-0661(05)80309-3}, booktitle={Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK)}, publisher={Elsevier}, author={Gadducci, Fabio and Heckel, Reiko and Llabrés, Mercé}, year={1999}, pages={80–100}, collection={Electronic Notes in Theoretical Computer Science} }
Gadducci, Fabio, Reiko Heckel, and Mercé Llabrés. “A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting.” In Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK), 29:80–100. Electronic Notes in Theoretical Computer Science. Elsevier, 1999. http://dx.doi.org/10.1016/S1571-0661(05)80309-3.
F. Gadducci, R. Heckel, and M. Llabrés, “A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting,” in Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK), 1999, vol. 29, pp. 80–100.
Gadducci, Fabio, et al. “A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting.” Proceedings of the 8th Conference on Category Theory and Computer Science (CTCS 1999), Edinburgh (UK), vol. 29, Elsevier, 1999, pp. 80–100, doi:http://dx.doi.org/10.1016/S1571-0661(05)80309-3.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar