Adhesive and quasiadhesive categories

Stephen Lack; Paweł Sobociński

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

  • Volume: 39, Issue: 3, page 511-545
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Lack, Stephen, and Sobociński, Paweł. "Adhesive and quasiadhesive categories." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.3 (2005): 511-545. <http://eudml.org/doc/245558>.

@article{Lack2005,
abstract = {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.},
author = {Lack, Stephen, Sobociński, Paweł},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {adhesive categories; quasiadhesive categories; extensive categories; category theory; graph rewriting},
language = {eng},
number = {3},
pages = {511-545},
publisher = {EDP-Sciences},
title = {Adhesive and quasiadhesive categories},
url = {http://eudml.org/doc/245558},
volume = {39},
year = {2005},
}

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
PB - EDP-Sciences
VL - 39
IS - 3
SP - 511
EP - 545
AB - 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.
LA - eng
KW - adhesive categories; quasiadhesive categories; extensive categories; category theory; graph rewriting
UR - http://eudml.org/doc/245558
ER -

References

top
  1. [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. [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. Zbl0882.18005
  3. [3] A. Carboni, S. Lack and R.F.C. Walters, Introduction to extensive and distributive categories. J. Pure Appl. Algebra 84 (1993) 145–158. Zbl0784.18001
  4. [4] L. Cardelli, Bitonal membrane systems. Draft (2003). 
  5. [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. [6] V. Danos and C. Laneve, Graphs for core molecular biology, in International Workshop on Computational Methods in Systems Biology, CMSB ’03 (2003). Zbl1053.92021
  7. [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. Zbl0407.68072
  8. [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). Zbl0998.68001MR1734027
  9. [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. [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. Zbl0765.68088
  11. [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). Zbl0749.68045MR1146599
  12. [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. Zbl1126.68446
  13. [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). Zbl0951.68049MR1730474
  14. [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. [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). Zbl1260.68094
  16. [16] H.-J. Kreowski, Transformations of derivation sequences in graph grammars. Lect. Notes Comput. Sci. 56 (1977) 275–286. Zbl0356.68085
  17. [17] S. Lack and P. Sobociński, Adhesive categories, in Proceedings of FOSSACS ’04, Springer. Lect. Notes Comput. Sci. 2987 (2004) 273–288. Zbl1126.68447
  18. [18] S. Lack and P. Sobociński, Quasitoposes, quasiadhesive categories and Artin glueing, in preparation (2005). Zbl1214.18003
  19. [19] J. Lambek and P.J. Scott, Introduction to higher order categorical logic, Cambridge studies in advanced mathematics. Cambridge University Press 7 (1986). Zbl0596.03002MR856915
  20. [20] R. Milner, Bigraphical reactive systems: Basic theory, Technical Report 523, Computer Laboratory, University of Cambridge (2001). Zbl1006.68080MR1905465
  21. [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. [22] G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Tranformation, Volume 1: Foundations. World Scientific (1997). Zbl0908.68095MR1480952
  23. [23] V. Sassone and P. Sobociński, Deriving bisimulation congruences using 2-categories. Nordic J. Comput. 10 (2003) 163–183. Zbl1062.68082
  24. [24] V. Sassone and P. Sobociński, Congruences for contextual graph-rewriting, Technical Report RS-04-11, BRICS, University of Aarhus (June 2004). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.