Spans, trees and minimal realization

Bob Rosebrugh – 10 February 1999

Recently Katis, Sabadini and Walters have proposed the (discrete, cartesian) bicategory of spans of directed graphs as a suitable algebra for concurrent computation. We propose trees as behaviours for a pointed version of the spans. After restricting to a suitable (non-full) subcategory reachable spans, we find a minimal realization. This is joint work with N. Sabadini and R. Walters