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] 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.
, , , , and ,[2] Van Kampen theorems for categories of covering morphisms in lextensive categories. J. Pure Appl. Algebra 119 (1997) 255-263. | Zbl
and ,[3] Introduction to extensive and distributive categories. J. Pure Appl. Algebra 84 (1993) 145-158. | Zbl
, and ,[4] Bitonal membrane systems. Draft (2003).
,[5] 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.
, , , , and ,[6] Graphs for core molecular biology, in International Workshop on Computational Methods in Systems Biology, CMSB '03 (2003). | Zbl
and ,[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] Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages and Tools. World Scientific (1999). | MR | Zbl
, , and , editors,[9] 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.
, and ,[10] 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
, , and ,[11] Parallelism and concurrency in high-level replacement systems. Math. Struct. Comp. Sci. 1 (1991). | MR | Zbl
, , and ,[12] 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
and ,[13] Handbook of Graph Grammars and Computing by Graph Transformation, Volume 3: Concurrency, Parallelism and Distribution. World Scientific (1999). | MR | Zbl
, , and , editors,[14] Graph-grammars: an algebraic approach, in IEEE Conf. on Automata and Switching Theory (1973) 167-180.
, and ,[15] A concurrent graph semantics for mobile ambients, in Mathematical Foundations of Programming Semantics MFPS '01, ENTCS. Elsevier 45 (2001).
and ,[16] Transformations of derivation sequences in graph grammars. Lect. Notes Comput. Sci. 56 (1977) 275-286. | Zbl
,[17] Adhesive categories, in Proceedings of FOSSACS '04, Springer. Lect. Notes Comput. Sci. 2987 (2004) 273-288. | Zbl
and ,[18] Quasitoposes, quasiadhesive categories and Artin glueing, in preparation (2005).
and ,[19] Introduction to higher order categorical logic, Cambridge studies in advanced mathematics. Cambridge University Press 7 (1986). | MR | Zbl
and ,[20] Bigraphical reactive systems: Basic theory, Technical Report 523, Computer Laboratory, University of Cambridge (2001). | MR | Zbl
,[21] 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.
, and ,[22] Handbook of Graph Grammars and Computing by Graph Tranformation, Volume 1: Foundations. World Scientific (1997). | MR | Zbl
, editor,[23] Deriving bisimulation congruences using 2-categories. Nordic J. Comput. 10 (2003) 163-183. | Zbl
and ,[24] Congruences for contextual graph-rewriting, Technical Report RS-04-11, BRICS, University of Aarhus (June 2004).
and ,Cité par Sources :