Abstract
Adhesive categories provide an abstract framework for the algebraic approach to rewriting theory, where many general results can be recast and uniformly proved. However, checking that a model satisfies the adhesivity properties is sometimes far from immediate. In this paper we present a new criterion giving a sufficient condition for \(\mathcal {M},\mathcal {N}\)-adhesivity, a generalisation of the original notion of adhesivity. We apply it to several existing categories, and in particular to hierarchical graphs, a formalism that is notoriously difficult to fit in the mould of algebraic approaches to rewriting and for which various alternative definitions float around.
Work supported by the Italian MIUR project PRIN 2017FTXR7S “IT-MaTTerS”.
Chapter PDF
Similar content being viewed by others
References
J. Adámek, H. Herrlich, and G. E. Strecker. Abstract and concrete categories: The joy of cats. Reprints in Theory and Applications of Categories, 17:1–507, 2006.
G. G. Azzi, A. Corradini, and L. Ribeiro. On the essence and initiality of conflicts in \(\cal{M}\)-adhesive transformation systems. Journal of Logical and Algebraic Methods in Programming, 109:100482, 2019.
G. Bacci, D. Grohmann, and M. Miculan. DBtk: A toolkit for directed bigraphs. In A. Kurz, M. Lenisa, and A. Tarlecki, editors, CALCO 2009, volume 5728 of LNCS, pages 413–422. Springer, 2009.
F. Burco, M. Miculan, and M. Peressotti. Towards a formal model for composable container systems. In C. Hung, T. Cerný, D. Shin, and A. Bechini, editors, SAC 2020, pages 173–175. ACM, 2020.
A. Carboni and P. Johnstone. Connected limits, familial representability and Artin glueing. Mathematical Structures in Computer Science, 5(4):441–459, 1995.
D. Castelnovo, F. Gadducci, and M. Miculan. A new criterion for \(\cal{M},\cal{N}\)-adhesivity, with an application to hierarchical graphs. CoRR, abs/2201.00233, 2022.
A. Corradini and F. Gadducci. On term graphs as an adhesive category. In M. Fernández, editor, TERMGRAPH 2004, volume 127(5) of ENTCS, pages 43–56. Elsevier, 2005.
A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, and M. Löwe. Algebraic approaches to graph transformation - Part I: Basic concepts and double pushout approach. In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, pages 163–246. World Scientific, 1997.
H. Ehrig, K. Ehrig, U. Prange, and G. Taentzer. Fundamentals of Algebraic Graph Transformation. Springer, 2006.
H. Ehrig, A. Habel, H.-J. Kreowski, and F. Parisi-Presicce. Parallelism and concurrency in high-level replacement systems. Mathematical Structures in Computer Science, 1(3):361–404, 1991.
H. Ehrig, A. Habel, J. Padberg, and U. Prange. Adhesive high-level replacement categories and systems. In H. Ehrig, G. Engels, F. Parisi-Presicce, and G. Rozenberg, editors, ICGT 2004, LNCS, pages 144–160. Springer, 2004.
R. Garner and S. Lack. On the axioms for adhesive and quasiadhesive categories. Theory and Applications of Categories, 27(3):27–46, 2012.
D. Grohmann and M. Miculan. Directed bigraphs. In M. Fiore, editor, MFPS 2007, volume 173 of ENTCS, pages 121–137. Elsevier, 2007.
A. Habel and D. Plump. \(\cal{M}\), \(\cal{N}\)-adhesive transformation systems. In H. Ehrig, G. Engels, H. Kreowski, and G. Rozenberg, editors, ICGT 2012, volume 7562 of LNCS, pages 218–233. Springer, 2012.
P. T. Johnstone, S. Lack, and P. Sobocinski. Quasitoposes, quasiadhesive categories and Artin glueing. In T. Mossakowski, U. Montanari, and M. Haveraaen, editors, CALCO 2007, volume 4624 of LNCS, pages 312–326. Springer, 2007.
S. Lack and P. Sobociński. Adhesive and quasiadhesive categories. RAIRO-Theoretical Informatics and Applications, 39(3):511–545, 2005.
S. Lack and P. Sobocinski. Toposes are adhesive. In A. Corradini, H. Ehrig, U. Montanari, L. Ribeiro, and G. Rozenberg, editors, ICGT 2006, volume 4178 of LNCS, pages 184–198. Springer, 2006.
T. Leinster. Higher operads, higher categories. Cambridge University Press, 2004.
S. Mac Lane. Categories for the working mathematician. Springer, 2013.
R. Milner. The Space and Motion of Communicating Agents. Cambridge University Press, 2009.
N. Mylonakis and F. Orejas. A framework of hierarchical graphs and its application to the semantics of SRML. Technical Report LSI-12-1-R, Facultad de Informática, Universitat Politècnica da Catalunya, 2012.
nLab. Creation of limits, 2016. Last accessed on January 26, 2022. http://nlabpages.s3.us-east-2.amazonaws.com/nlab/show/created+limit.
J. Padberg. Hierarchical graph transformation revisited - Transformations of coalgebraic graphs. In J. de Lara and D. Plump, editors, ICGT 2017, volume 10373 of LNCS, pages 20–35. Springer, 2017.
W. Palacz. Algebraic hierarchical graph transformation. Journal of Computer and System Sciences, 68(3):497–520, 2004.
C. Peuser and A. Habel. Composition of \(\cal{M},\cal{N}\)-adhesive categories with application to attribution of graphs. In D. Plump, editor, GCM 2015, volume 73 of Electronic Communications of the EASST. EASST, 2016.
D. Plump. Term graph rewriting. In H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 2: Applications, Languages, and Tools, pages 3–61. World Scientific, 1999.
M. Sevegnani and M. Calder. Bigraphs with sharing. Theoretical Computer Science, 577:43–73, 2015.
P. Sobociński and N. Behr. Rule algebras for adhesive categories. Logical Methods in Computer Science, 16, 2020.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2022 The Author(s)
About this paper
Cite this paper
Castelnovo, D., Gadducci, F., Miculan, M. (2022). A new criterion for \(\mathcal {M}, \mathcal {N}\)-adhesivity, with an application to hierarchical graphs. In: Bouyer, P., Schröder, L. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2022. Lecture Notes in Computer Science, vol 13242. Springer, Cham. https://doi.org/10.1007/978-3-030-99253-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-99253-8_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-99252-1
Online ISBN: 978-3-030-99253-8
eBook Packages: Computer ScienceComputer Science (R0)