Algebraic foundations for higraphs and statecharts

Konstantinos Tourlas – 23 January 2002

Higraphs, a kind of hierarchical graphs, are prominent structures in computing, underlying a number of sophisticated diagrammatic formalisms such as Statecharts and UML. Starting with a formalisation of higraphs as graphs in the category Poset, we explore the universal properties associated with a number of practically important operations on higraphs, such "zooming" and "completion". Further, the symmetric monoidal closed structure of the category H of higraphs will be exposed and related to the so-called "other" such structure on Cat. Brief excursion will be made on how the study of higraphs motivates the study of Graphs(C), the category of graphs in a locally ordered category C, and on how many higraph-specific results arise in this more general setting. Time permitting, general issues pertaining to a theory of diagrammatic notations in computing will be discussed. I would like to encourage questions and discussion during the talk rather than stick to a firm agenda.