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.
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}},
title = {Adhesive and quasiadhesive categories},
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ł TI - Adhesive and quasiadhesive categories JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 511 EP - 545 VL - 39 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2005028/ DO - 10.1051/ita:2005028 LA - en ID - ITA_2005__39_3_511_0 ER -
%0 Journal Article %A Lack, Stephen %A Sobociński, Paweł %T Adhesive and quasiadhesive categories %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 511-545 %V 39 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2005028/ %R 10.1051/ita:2005028 %G en %F ITA_2005__39_3_511_0
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] ,,,, and, 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] and, Van Kampen theorems for categories of covering morphisms in lextensive categories. J. Pure Appl. Algebra 119 (1997) 255-263. | Zbl
[3] , and, Introduction to extensive and distributive categories. J. Pure Appl. Algebra 84 (1993) 145-158. | Zbl
[4] , Bitonal membrane systems. Draft (2003).
[5] ,,,, and, 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] and, Graphs for core molecular biology, in International Workshop on Computational Methods in Systems Biology, CMSB '03 (2003). | Zbl
[7] , 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
[8] ,, and, editors, Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages and Tools. World Scientific (1999). | MR | Zbl
[9] , and, 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] ,, and, 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
[11] ,, and, Parallelism and concurrency in high-level replacement systems. Math. Struct. Comp. Sci. 1 (1991). | MR | Zbl
[12] and, 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
[13] ,, and, editors, Handbook of Graph Grammars and Computing by Graph Transformation, Volume 3: Concurrency, Parallelism and Distribution. World Scientific (1999). | MR | Zbl
[14] , and, Graph-grammars: an algebraic approach, in IEEE Conf. on Automata and Switching Theory (1973) 167-180.
[15] and, A concurrent graph semantics for mobile ambients, in Mathematical Foundations of Programming Semantics MFPS '01, ENTCS. Elsevier 45 (2001).
[16] , Transformations of derivation sequences in graph grammars. Lect. Notes Comput. Sci. 56 (1977) 275-286. | Zbl
[17] and, Adhesive categories, in Proceedings of FOSSACS '04, Springer. Lect. Notes Comput. Sci. 2987 (2004) 273-288. | Zbl
[18] and, Quasitoposes, quasiadhesive categories and Artin glueing, in preparation (2005).
[19] and, Introduction to higher order categorical logic, Cambridge studies in advanced mathematics. Cambridge University Press 7 (1986). | MR | Zbl
[20] , Bigraphical reactive systems: Basic theory, Technical Report 523, Computer Laboratory, University of Cambridge (2001). | MR | Zbl
[21] , and, 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] , editor, Handbook of Graph Grammars and Computing by Graph Tranformation, Volume 1: Foundations. World Scientific (1997). | MR | Zbl
[23] and, Deriving bisimulation congruences using 2-categories. Nordic J. Comput. 10 (2003) 163-183. | Zbl
[24] and, Congruences for contextual graph-rewriting, Technical Report RS-04-11, BRICS, University of Aarhus (June 2004).
Cité par Sources :
