Monographs and Their Role in Universal Graph Representation

:::info Author:

(1) Thierry Boy de la Tour, Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG 38000 Grenoble, France.

:::

Abstract and 1 Introduction

2 Basic Definitions and Notations

2.1 Sets

2.2 Sequences

2.3 Signatures and Algebras and 2.4 Categories

3 Monographs and their Morphisms

4 Limits and Colimits

5 Drawing Monographs

6 Graph Structures and Typed Monographs

7 Submonographs and Partial Morphisms

8 Algebraic Transformations of Monographs

9 Attributed Typed Monographs

10 Conclusion and References

Monographs generalize standard notions of directed graphs by allowing edges of any length with free adjacencies. An edge of length zero represents a node, and if it has greater length it can be adjacent to any edge, including itself. In “monograph” the prefix mono- is justified by this unified view of nodes as edges and of edges with unrestricted adjacencies that provide formal conciseness (morphisms are functions characterized by a single equation); the suffix -graph is justified by the correspondence (up to isomorphism) between finite ω-monographs and their drawings.

\ Monographs are universal with respect to graph structures and the corresponding algebras, in the sense that monographs are equivalent to graph structures extended with suitable ordering conventions on their operator names, and that categories of typed monographs are equivalent to the corresponding categories of algebras. Since many standard or exotic notions of directed graphs can be represented as monadic algebras, they can also be represented as typed monographs, but these have two advantages over graph structures: they provide an orientation of edges and they (consequently) dispense with operator names.

\ Algebraic transformations of monographs are similar to those of standard graphs. Typed monographs may therefore be simpler to handle than graph structured algebras, as illustrated by the results of Section 9. The representation of oriented edges as sequences seems more natural than their standard representation as unstructured objects that have images by a bunch of functions. Thus type monographs emerge as a natural way of specifying graph structures.

[1] T. Boy de la Tour, R. Echahed, Parallel rewriting of attributed graphs, Theoretical Computer Science 848 (2020) 106–132.

\ [2] H. Ehrig, K. Ehrig, U. Prange, G. Taentzer, Fundamentals of Algebraic Graph Transformation, Monographs in Theoretical Computer Science. An EATCS Series, Springer, 2006.

\ [3] M. Lowe, Algebraic approach to single-pushout graph transformation, Theoretical Computer Science 109 (1993) 181–224.

\ [4] T. Boy de la Tour, Monographs, a category of graph structures, in: Recent Trends in Algebraic Development Techniques, 25th International Workshop, WADT 2020, Revised Selected Papers, Vol. 12669 of LNCS, Springer, 2021, pp. 54–74.

\ [5] P. Suppes, Axiomatic Set Theory, Dover Publications, Inc., 1972.

\ [6] D. Sannella, A. Tarlecki, Foundations of Algebraic Specification and Formal Software Development, Monographs in Theoretical Computer Science. An EATCS Series, Springer, 2012.

\ [7] H. Herrlich, G. E. Strecker, Category Theory, 3rd Edition, Heldermann Verlag, Berlin, 2007.

\ [8] S. Lack, P. Sobocinski, Adhesive and quasiadhesive categories, Informatique Theorique et Applications 39 (3) (2005) 511–545.

\ [9] D. Plump, Term graph rewriting, in: H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg (Eds.), Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages and Tools, World Scientific, 1999, pp. 3–61.

\ [10] A. Burroni, Higher-dimensional word problems with applications to equational logic, Theoretical Computer Science 115 (1) (1993) 43–62.

\ [11] E. Robinson, G. Rosolini, Categories of partial maps, Information and Computation 79 (2) (1988) 95–130.

\ [12] A. Corradini, T. Heindel, F. Hermann, B. K¨onig, Sesqui-pushout rewriting, in: ICGT 2006, Vol. 4178 of LNCS, Springer, 2006, pp. 30–45.

\ [13] A. Corradini, D. Duval, R. Echahed, F. Prost, L. Ribeiro, AGREE - algebraic graph rewriting with controlled embedding, in: 8th ICGT, Vol. 9151 of LNCS, Springer, 2015, pp. 35–51.

\ [14] A. Corradini, D. Duval, R. Echahed, F. Prost, L. Ribeiro, The PBPO graph transformation approach, J. Log. Algebr. Meth. Program. 103 (2019) 213– 231.

\ [15] T. Boy de la Tour, R. Echahed, Parallel coherent graph transformations, in: Recent Trends in Algebraic Development Techniques, 25th International Workshop, WADT 2020, Revised Selected Papers, Vol. 12669 of LNCS, Springer, 2021, pp. 75–97.

\ [16] H. Ehrig, M. Pfender, H. J. Schneider, Graph-grammars: An algebraic approach, in: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, 1973, pp. 167–180.

\ [17] A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, M. Lowe, Algebraic approaches to graph transformation - part I: basic concepts and double pushout approach, World Scientific, 1997, pp. 163–246.

\ [18] A. Habel, J. Muller, D. Plump, Double-pushout graph transformation revisited, Math. Struct. Comput. Sci 11 (5) (2001) 637–688.

\ [19] J.-C. Raoult, On graph rewritings, Theoretical Computer Science 32 (1,2) (1984) 1–24.

\ [20] M. Lowe, Extended algebraic graph transformation, Ph.D. thesis, Technical University of Berlin, Germany (1991).

\ [21] M. Lowe, M. Korff, A. Wagner, An algebraic framework for the transformation of attributed graphs, in: R. Sleep, R. Plasmeijer, M. van Eekelen (Eds.), Term Graph Rewriting: Theory and Practice, John Wiley, New York, 1993, pp. 185–199.

\ [22] R. Heckel, J. M. K¨uster, G. Taentzer, Confluence of typed attributed graph transformation systems, in: A. Corradini, H. Ehrig, H. Kreowski, G. Rozenberg (Eds.), Graph Transformation, First International Conference ICGT 2002, Vol. 2505 of LNCS, Springer, 2002, pp. 161–176.

\ [23] H. Ehrig, K. Ehrig, U. Prange, G. Taentzer, Fundamental theory for typed attributed graphs and graph transformation based on adhesive HLR categories, Fundam. Informaticae 74 (1) (2006) 31–61.

\ [24] H. Ehrig, J. Padberg, U. Prange, A. Habel, Adhesive high-level replacement systems: A new categorical framework for graph transformation, Fundam. Informaticae 74 (1) (2006) 1–29.

\

:::info This paper is available on arxiv under CC BY 4.0 DEED license.

:::

\