RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 3, pp. 511-545.

We introduce adhesive categories, which are categories with structure ensuring that pushouts along monomorphisms are well-behaved, as well as quasiadhesive categories which restrict attention to regular monomorphisms. Many examples of graphical structures used in computer science are shown to be examples of adhesive and quasiadhesive categories. Double-pushout graph rewriting generalizes well to rewriting on arbitrary adhesive and quasiadhesive categories.

DOI : https://doi.org/10.1051/ita:2005028
Classification : 18A30,  18A35,  18D99,  68Q42,  68Q65
Mots clés : adhesive categories, quasiadhesive categories, extensive categories, category theory, graph rewriting
@article{ITA_2005__39_3_511_0,
author = {Lack, Stephen and Soboci\'nski, Pawe{\l}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {511--545},
publisher = {EDP-Sciences},
volume = {39},
number = {3},
year = {2005},
doi = {10.1051/ita:2005028},
zbl = {1078.18010},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2005028/}
}
TY  - JOUR
AU  - Lack, Stephen
AU  - Sobociński, Paweł
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2005
DA  - 2005///
SP  - 511
EP  - 545
VL  - 39
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2005028/
UR  - https://zbmath.org/?q=an%3A1078.18010
UR  - https://doi.org/10.1051/ita:2005028
DO  - 10.1051/ita:2005028
LA  - en
ID  - ITA_2005__39_3_511_0
ER  - 
Lack, Stephen; Sobociński, Paweł. Adhesive and quasiadhesive categories. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 3, pp. 511-545. doi : 10.1051/ita:2005028. http://www.numdam.org/articles/10.1051/ita:2005028/

[1] P. Baldan, A. Corradini, H. Ehrig, M. Löwe, U. Montanari and F. Rossi, Concurrent semantics of algebraic graph transformations, in Handbook of Graph Grammars and Computing by Graph Transformation, edited by H. Ehrig, H.-J. Kreowski, U. Montanari and G. Rozenberg, World Scientific 3 (1999) 107-187.

[2] R. Brown and G. Janelidze, Van Kampen theorems for categories of covering morphisms in lextensive categories. J. Pure Appl. Algebra 119 (1997) 255-263. | Zbl 0882.18005

[3] A. Carboni, S. Lack and R.F.C. Walters, Introduction to extensive and distributive categories. J. Pure Appl. Algebra 84 (1993) 145-158. | Zbl 0784.18001

[4] L. Cardelli, Bitonal membrane systems. Draft (2003).

[5] A. Corradini, H. Ehrig, R. Heckel, M. Lowe, U. Montanari and F. Rossi, Algebraic approaches to graph transformation part i: Basic concepts and double pushout approach, in Handbook of Graph Grammars and Computing by Graph Transformation, edited by G. Rozenberg, World Scientific 1 (1997) 162-245.

[6] V. Danos and C. Laneve, Graphs for core molecular biology, in International Workshop on Computational Methods in Systems Biology, CMSB '03 (2003). | Zbl 1053.92021

[7] H. Ehrig, Introduction to the algebraic theory of graph grammars, in 1st Int. Workshop on Graph Grammars, Springer Verlag. Lect. Notes Comput. Sci. 73 (1979) 1-69. | Zbl 0407.68072

[8] H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages and Tools. World Scientific (1999). | MR 1734027 | Zbl 0998.68001

[9] H. Ehrig, M. Gajewsky and F. Parisi-Presicce, High-level replacement systems with applications to algebraic specificaitons and Petri Nets, in Handbook of Graph Grammars and Computing by Graph Transformation, edited by H. Ehrig, H.-J. Kreowsky, U. Montanari and G. Rozenberg, World Scientific 3 (1999) 341-400.

[10] H. Ehrig, A. Habel, H.-J. Kreowski and F. Parisi-Presicce, From graph grammars to high level replacement systems, in 4th Int. Workshop on Graph Grammars and their Application to Computer Science, Springer-Verlag. Lect. Notes Comp. Sci. 532 (1991) 269-291. | Zbl 0765.68088

[11] H. Ehrig, A. Habel, H.-J. Kreowski and F. Parisi-Presicce, Parallelism and concurrency in high-level replacement systems. Math. Struct. Comp. Sci. 1 (1991). | MR 1146599 | Zbl 0749.68045

[12] H. Ehrig and B. König, Deriving bisimulation congruences in the dpo approach to graph rewriting, in Foundations of Software Science and Computation Structures FoSSaCS '04, Springer. Lect. Notes Comput. Sci. 2987 (2004) 151-166. | Zbl 1126.68446

[13] H. Ehrig, H.-J. Kreowski, U. Montanari and G. Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformation, Volume 3: Concurrency, Parallelism and Distribution. World Scientific (1999). | MR 1730474 | Zbl 0951.68049

[14] H. Ehrig, M. Pfender and H.J. Schneider, Graph-grammars: an algebraic approach, in IEEE Conf. on Automata and Switching Theory (1973) 167-180.

[15] F. Gadducci and U. Montanari, A concurrent graph semantics for mobile ambients, in Mathematical Foundations of Programming Semantics MFPS '01, ENTCS. Elsevier 45 (2001).

[16] H.-J. Kreowski, Transformations of derivation sequences in graph grammars. Lect. Notes Comput. Sci. 56 (1977) 275-286. | Zbl 0356.68085

[17] S. Lack and P. Sobociński, Adhesive categories, in Proceedings of FOSSACS '04, Springer. Lect. Notes Comput. Sci. 2987 (2004) 273-288. | Zbl 1126.68447

[18] S. Lack and P. Sobociński, Quasitoposes, quasiadhesive categories and Artin glueing, in preparation (2005).

[19] J. Lambek and P.J. Scott, Introduction to higher order categorical logic, Cambridge studies in advanced mathematics. Cambridge University Press 7 (1986). | MR 856915 | Zbl 0596.03002

[20] R. Milner, Bigraphical reactive systems: Basic theory, Technical Report 523, Computer Laboratory, University of Cambridge (2001). | MR 1905465 | Zbl 1006.68080

[21] U. Montanari, M. Pistore and F. Rossi, Modelling concurrent, mobile and coordinated systems via graph transformations, in Handbook of Graph Grammars and Computing by Graph Transformation, edited by H. Ehrig, H.-J. Kreowski, U. Montanari and G. Rozenberg, World Scientific 3 (1999) 189-268.

[22] G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Tranformation, Volume 1: Foundations. World Scientific (1997). | MR 1480952 | Zbl 0908.68095

[23] V. Sassone and P. Sobociński, Deriving bisimulation congruences using 2-categories. Nordic J. Comput. 10 (2003) 163-183. | Zbl 1062.68082

[24] V. Sassone and P. Sobociński, Congruences for contextual graph-rewriting, Technical Report RS-04-11, BRICS, University of Aarhus (June 2004).

Cité par Sources :