The Algebra of Everything

Table of Links

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

Abstract

Monographs are graph-like structures with directed edges of unlimited length that are freely adjacent to each other. The standard nodes are represented as edges of length zero. They can be drawn in a way consistent with standard graphs and many others, like E-graphs or 8-graphs. The category of monographs share many properties with the categories of graph structures (algebras of monadic many-sorted signatures), except that there is no terminal monograph. It is universal in the sense that its slice categories (or categories of typed monographs) are equivalent to the categories of graph structures. Type monographs thus emerge as a natural way of specifying graph structures. A detailed analysis of single and double pushout transformations of monographs is provided, and a notion of attributed typed monographs generalizing typed attributed E-graphs is analyzed w.r.t. attribute-preserving transformations.

Keywords: Algebraic Graph Transformation, Graph Structures, Typed Graphs

1 Introduction

Many different notions of graphs are used in mathematics and computer science: simple graphs, directed graphs, multigraphs, hypergraphs, etc. One favourite notion in the context of logic and rewriting is that also known as quivers, i.e., structures of the form pN, E, s, tq where N, E are sets and s, t are functions from E (edges) to N (nodes), identifying the source and target tips of every edge (or arrow). One reason for this is that the category of quivers is isomorphic to the category of algebras of the many-sorted signature with two sorts nodes and edges and two operator names src and tgt of type edges Ñ nodes. In conformity with this tradition, by graph we mean quiver throughout this paper.

In order to conveniently represent elaborate data structures it is often necessary to enrich the structure of graphs with attributes: nodes or edges may be labelled with elements from a fixed set, or with values taken in some algebra, or with sets of values as in [1], etc. An interesting example can be found in [2] with the notion of E-graphs, since the attributes are also considered as nodes.

More precisely, an E-graph is an algebra whose signature can be represented by the following graph:

The names given to the sorts and operators help to understand the structure of E-graphs: the edges relate the nodes among themselves, the nv-edges relate the nodes to the values, and the ev-edges relate the edges to the values. Hence the sort values holds attributes that are also nodes. But then we see that in E-graphs the ev-edges are adjacent to edges. This is non standard, but we may still accept such structures as some form of graph, if only because we understand how they can be drawn.

Hence the way of generalizing the notion of graphs seems to involve a generalization of the signature of graphs considered as algebras. This path has been followed by Michael L¨owe in [3], where a graph structure is defined as a monadic many-sorted signature. Indeed in the examples above, and in many examples provided in [3], all operators have arity 1 and can therefore be considered as edges from their domain to their range sort. Is this the reason why they are called graph structures? But the example above shows that E-graphs are very different from the graph that represent their signature. Besides, it is not convenient that our understanding of such structures should be based on syntax, i.e., on the particular names given to sorts and operators in the signature.

Furthermore, it is difficult to see how the algebras of some very simple monadic signatures can be interpreted as graphs of any form. Take for instance the signature of graphs and reverse the target function to tgt : nodes Ñ edges. Then there is a symmetry between the sorts nodes and edges, which means that in an algebra of this signature nodes and edges would be objects of the same nature. Is this still a graph? Can we draw it? Worse still, if the two sorts are collapsed into one, does it mean that a node/edge can be adjacent to itself?

We may address these problems by restricting graph structures to some class of monadic signatures whose algebras are guaranteed to behave in an orthodox way, say by exhibiting clearly separated edges and nodes. But this could be prone to arbitrariness, and it would still present another drawback: that the notion of graph structure does not easily give rise to a category. Indeed, it is difficult to define morphisms between algebras of different signatures, if only because they can have any number of carrier sets.

The approach adopted here is rather to reject any structural distinction between nodes and edges, hence to adopt a unified view of nodes as edges of length 0, and standard edges as edges of length 2 since they are adjacent to two nodes. This unified view logically allows edges to be adjacent to any edges and not just to nodes, thus generalizing the ev-edges of E-graphs, and even to edges that are adjacent to themselves. Finally, there is no reason to restrict the length of edges to 0 or 2, and we will find good reasons (in Section 6) for allowing edges of infinite, ordinal length. The necessary notions and notations are introduced in Section 2. The structure of monograph (together with morphisms) is defined in Section 3, yielding a bestiary of categories of monographs according to some of their characteristics. The properties of these categories w.r.t. the existence of limits and co-limits are analyzed in Section 4.

We then see in Section 5 how monographs can be accurately represented by drawings, provided of course that they have finitely many edges and that these have finite length. In particular, such drawings correspond to the standard way of drawing a graph for those monographs that can be identified with standard graphs, and similarly for E-graphs.

Section 6 is devoted to the comparison between monographs and graph structures, and the corresponding algebras (that we may call graph structured algebras). We show a property of universality of monographs, in the sense that all graph structured algebras can be represented (though usually not in a canonical way) as typed monographs, i.e., as morphisms of monographs.

The notion of graph structure has been introduced in [3] in order to obtain categories of partial homomorphisms in which techniques of algebraic graph rewriting could be carried out. The correspondence with monographs established in Section 6 calls for a similar development of partial morphisms of monographs in Section 7. The single and double pushout methods of rewriting monographs can then be defined, analyzed and compared in Section 8.

The notion of E-graph has been introduced in [2] in order to obtain wellbehaved categories (w.r.t. graph rewriting) of attributed graphs, and hence to propose suitable representations of real-life data structures. This is achieved by enriching E-graphs with a data type algebra, and by identifying nodes of sort value with the elements of this algebra. We pursue a similar approach in Section 9 with the notion of attributed typed monograph by identifying elements of an algebra with edges, and obtain similarly well-behaved categories. Due to the universality of monographs we see that any Σ-algebra can be represented as an attributed typed monograph.

We conclude in Section 10. Note that parts of Sections 4 to 6 have been published in [4].