---
_id: '7858'
abstract:
- lang: eng
text: 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.
author:
- first_name: Fabio
full_name: Gadducci, Fabio
last_name: Gadducci
- first_name: Reiko
full_name: Heckel, Reiko
last_name: Heckel
- first_name: Mercé
full_name: Llabrés, Mercé
last_name: Llabrés
citation:
ama: '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'
apa: 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
bibtex: '@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} }'
chicago: 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.
ieee: 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.
mla: 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.
short: '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.'
date_created: 2019-02-20T14:36:57Z
date_updated: 2019-02-20T14:37:28Z
department:
- _id: '66'
doi: http://dx.doi.org/10.1016/S1571-0661(05)80309-3
intvolume: ' 29'
language:
- iso: eng
page: 80-100
publication: Proceedings of the 8th Conference on Category Theory and Computer Science
(CTCS 1999), Edinburgh (UK)
publisher: Elsevier
series_title: Electronic Notes in Theoretical Computer Science
status: public
title: A Bi-Categorical Axiomatisation of Concurrent Graph Rewriting
type: conference
user_id: '52534'
volume: 29
year: '1999'
...