9
$\begingroup$

On the surface, it would seem that category theory would be a very natural and useful mathematical tool to address the subject of graph transformation. Yet, early indications from online searches seem to indicate that it hasn't received much use in practice. The most cited work seems to point to Minas and Schneider in "Graph Transformation by Computational Category Theory".

This leads me to wonder why the "natural" semantics of morphisms in category theory and the $Grph$ category are not exploited more broadly for this purpose. After briefly surveying Minas and Schneirder's paper, I did not see it as a powerful and concise tool for graph transforms. The use of boolean matrix algebra seems nearly as powerful, more concise, and highly efficient computationally.

I'm curious to know if the utility of category theory for this purpose is known to be weak, since I was interested in possibly using it as a foundation for some work. I'm interested in learning your insight and/or experience on this topic.

$\endgroup$
4
  • 1
    $\begingroup$ It's pretty unlikely that the utility of category theory for this purpose is known to be weak, simply because it's difficult to prove a negative. I've found that this kind of question is generally very difficult to answer satisfactorily, and such answers as exist often impinge on sociological as well as mathematical factors. $\endgroup$ Feb 7, 2015 at 19:55
  • $\begingroup$ I don't really see how category can be used to "implement" actual transformations, aside from drawing actual graphs in terms of objects and morphisms, and drawing a morphism/functor from one to the other. Which is nice, intuitive, and elegant, but also verbose. $\endgroup$
    – nomen
    Feb 7, 2015 at 22:56
  • $\begingroup$ Hmm, categories are really just big directed graphs, why isn't graph theory more prominent in the study of category theory? $\endgroup$ Feb 7, 2015 at 23:06
  • $\begingroup$ Well, categories are graphs with a "multiplication". $\endgroup$ Apr 7, 2015 at 23:25

2 Answers 2

3
$\begingroup$

Two categories can be equivalent and still the underlying graphs can be very different. In fact, one graph may be infinite and the other finite. The tools developed in category theory aim not to distinguish between the two categories. So category theory is designed to overlook some very important differences between graphs. See also http://ncatlab.org/nlab/show/principle+of+equivalence.

$\endgroup$
1
$\begingroup$

The difference between Category Theory and Graph Theory is the types of questions asked. So even though the formal mathematical structures are similar, in practice the subjects have little in common.

Category Theory captures abstract algebraic properties of constructions found throughout mathematics. On the other hand, Graph Theory has very little algebraic structure and instead revolves around combinatorial arguments. This is why there are several different graph products in use, even though there is only one categorical product of graphs.

$\endgroup$
2
  • $\begingroup$ I generally agree, but might not the same argument be made for sets? Their treatment is not algebraic; at least not chiefly. Yet, $Set$ is a very common category. My interest in the use of category theory was to allow for meaningful morphisms between the function and structure of systems (defined mathematically). The function of a subsystem is often more easily described algebraically, however, its structure is often best described in graph-theoretical form, hence my interest in using category theory as the basis for both, and the transformation from one to the other. Thoughts? $\endgroup$
    – Alan
    Feb 8, 2015 at 11:37
  • $\begingroup$ While Set is a common category, it is rarely used in algebraic arguments. In fact, a common theme in algebra is the categorification of properties from Set into more algebraic structures (i.e., replacing the integers with vector spaces of given dimension). Of course, if you're working on a specific result, use whatever tools are at your disposal. $\endgroup$
    – pre-kidney
    Feb 12, 2015 at 5:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .