Adhesivity with Partial Maps instead of Spans

• Autorzy: Heindel T.
• Języki publikacji: EN

Abstrakty

EN

The introduction of adhesive categories revived interest in the study of properties of pushouts with respect to pullbacks that started over thirty years ago for the category of graphs. Adhesive categories - of which graphs are the 'archetypal' example - are defined by a single property of pushouts along monos that implies essential lemmas and central theorems of double pushout rewriting such as the local Church-Rosser Theorem. The present paper shows that a strictly weaker condition on pushouts suffices to obtain essentially the same results: it suffices to require pushouts to be hereditary, i.e. they have to remain pushouts when they are embedded into the associated category of partial maps. This fact however is not the only reason to introduce partial map adhesive categories as categories with pushouts along monos (of a certain stable class) that are hereditary. There are two equally important motivations: first, there is an application relevant example category that cannot be captured by the more established variations of adhesive categories; second, partial map adhesive categories are 'conceptually similar' to adhesive categories as the latter can be characterized as those categories with pushout along monos that remain bi-pushouts when they are embedded into the associated bi-category of spans. Thus, adhesivity with partial maps instead of spans appears to be a natural candidate for a general rewriting framework.

Słowa kluczowe

EN

category theory; double pushout rewriting; graph transformation; single pushout rewriting; adhesive categories

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 118, nr 1-2
• Strony: 1--33
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Heindel T.

• Institut CARNOT CEA LIST, DILS/LMEASI, Commissariat a l'énergie atomique et aux énergies alternatives, 91191 Gif sur Yvette CEDEX, France,

Bibliografia

• [1] Adamek, J., Herrlich, H., Strecker, G. E.: Abstract and concrete categories: the joy of cats, Wiley, 1990.
• [2] Ehrig, H., Golas, U., Hermann, F.: Categorical Frameworks for Graph Transformation and HLR Systems Based on the DPO Approach, Bulletin of the EATCS, 102, 2010, 111-121.
• [3] Ehrig, H., Heckel, R., Korff, M., Lowe, M., Ribeiro, L., Wagner, A., Corradini, A.: Algebraic Approaches to Graph Transformation - Part II: Single Pushout Approach and Comparison with Double Pushout Approach, Handbook of Graph Grammars (G. Rozenberg, Ed.), World Scientific, 1997.
• [4] Ehrig, H., Kreowski, H.-J.: Pushout-Properties: An Analysis of Gluing Constructions for Graphs, Mathematis-che Nachrichten, 91, 1979, 135-149.
• [5] Ehrig, H., Lowe, M.: Categorical Principles, Techniques and Results for High-Level-Replacement Systems in Computer Science, Applied Categorical Structures, 1(1), 1993, 21-50.
• [6] Ehrig, H., Padberg, J., Prange, U., Habel, A.: Adhesive High-Level Replacement Systems: A New Categorical Framework for Graph Transformation, Fundamenta Informaticae, 74(1), 2006, 1-29.
• [7] Ehrig, H., Pfender, M., Schneider, H. J.: Graph-Grammars: An Algebraic Approach, 14th Annual Symposium on Switching and Automata Theory, Institute of Electrical and Electronics Engineers, 1973.
• [8] Ehrig, H., Prange, U.: Weak Adhesive High-Level Replacement Categories and Systems: A Unifying Framework for Graph and Petri Net Transformations, Essays Dedicated to Joseph A. Goguen (K. Futatsugi, J.-P. Jouannaud, J. Meseguer, Eds.), 4060, Springer, 2006.
• [9] Habel, A., Miiller, J., Plump, D.: Double-pushout graph transformation revisited, Mathematical Structures in Computer Science, 11(5), 2001, 637-688.
• [10] Heindel, T.: A Category Theoretical Approach to the Concurrent Semantics of Rewriting ~ Adhesive Categories and Related Concepts, Ph.D. Thesis, Universitat Duiburg-Essen, 2009.
• [11] Heindel, T.: Hereditary Pushouts Reconsidered, International Conference on Graph Transformation, ICGT 2010 (H. Ehrig, A. Rensink, G. Rozenberg, A. Schurr, Eds.), 6372, Springer, 2010.
• [12] Heindel, T., Sobocinski, P.: Being Van Kampen is a universal property, Logical Methods in Computer Science, 7(l),2011, 1-22.
• [13] Johnstone, P. T., Lack, S., Sobocinski, P.: Quasitoposes, quasiadhesive categories and Artin glueing, Algebra and Coalgebra in Computer Science, CALCO 2007, 4626, Springer, August 2007.
• [14] Kennaway, R.: Graph Rewriting in Some Categories of Partial Morphisms, Graph-Grammars and Their Application to Computer Science (H. Ehrig, H.-J. Kreowski, G. Rozenberg, Eds.), 532, Springer, 1990.
• [15] Lack, S., Sobocinski, P.: Adhesive Categories, FOSSACS (I. Walukiewicz, Ed.), 2987, Springer, 2004.
• [16] Lack, S., Sobocinski, P.: Adhesive and quasi adhesive categories, Theoretical Informatics and Applications, 39(2), 2005, 511-546.
• [17] Lowe, M.: Algebraic Approach to Single-Pushout Graph Transformation, Theoretical Computer Science, 109(1 &2), 1993, 181-224.
• [18] Mac Lane, S.: Categories for the Working Mathematician, Number 5 in Graduate Texts in Mathematics, Springer, 1998.
• [19] de Mol, M., Rensink, A.: On A Graph Formalism for Ordered Edges, Electronic Communications of the EASST, 29, 2010, 2-13.
• [20] Padberg, J.: Survey of High-Level Replacement Systems, Technical report, Technische Universitat Berlin, 1993.
• [21] Pierce, B.C.: Basic Category Theory for Computer Scientists, MYT Press, 1991.
• [22] Prange, U.: Algebraic High-Level Nets as Weak Adhesive HLR Categories, Electronic Communications of the EASST, 2, 2007, 1-13.
• [23] Robinson, E., Rosolini, G.: Categories of Partial Maps, Information and Computation, 79(2), 1988, 95-130.