Hypergraph Construction and Its Application to the Static Analysis of ...


Barbara König. Hypergraph construction and its application to the static analysis of concurrent systems. Mathematical Structures in Computer Science, 12:149–175, 2002.


We define a construction operation on hypergraphs based on a colimit and show that its expressiveness is equal to the graph expressions of Bauderon and Courcelle. We also demonstrate that by closing a set of rewrite rules under graph construction we obtain a notion of rewriting equivalent to the double-pushout approach of Ehrig. The usefulness of our approach for the compositional modelling of concurrent systems is then demonstrated by giving a semantics of process graphs—corresponding to a process calculus with mobility—and of Petri nets. Based on hypergraph construction, a method for the static analysis of process graphs, related to type systems, is introduced.

Suggested BibTeX entry:

    author = {Barbara K{\"o}nig},
    journal = {Mathematical Structures in Computer Science},
    pages = {149--175},
    title = {Hypergraph Construction and Its Application to the Static Analysis of Concurrent Systems},
    volume = {12},
    year = {2002}

Conference versionThis work is not available online here.
© University of Duisburg-Essen, Theoretical Computer Science group