98: Report No. FBI-HH-B-216, pages 1-38. Fachbereich Informatik, Universität Hamburg, 1998.
Abstract: In this paper, we study general properties of relational structures (RS) and their different types of quotients. Moreover, we show the applications to conflict-free elementary Petri net systems with concurrency and causal ordering, namely, causal nets and synchronization graphs. For such nets, we characterize the semantically consistent coarsenings by syntactic criteria (i.e. depending only on the net structure). Independently of the interpretation in terms of nets, the connection between cyclic and acyclic partial orders is demonstrated by means of windings; the orientation of cyclic orders in the sense of Stehr is characterized in full generality by density properties; we arrive at a complete axiomatization of oriented cyclic order.
Finally, the problem of faithfulness for quotients of RS is addressed; in the situation of windings, an effectively checkable sufficient condition for faithfulness is obtained.
Keywords: synchronization graphs, causal nets, non-sequential processes, concurrency, partial orders, cyclic orders, quotients..
Back to the Petri Nets Bibliography