On the Relative Expressiveness of Petri Nets, Event Structures and Process Algebras abstract)

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

In this talk I consider mappings from expressions in system description languages like CCS and CSP to Petri nets and vice versa. I recall two methods for associating a Petri net to such a process expression: the standard compositional approach where recursion is dealt with using fixed point techniques, and a variant due to Ursula Goltz in which recursion is implemented by redirecting arcs backwards to initial places. The former approach always yields a so-called safe flow net; recursion typically gives rise to infinite nets. The latter approach works for the subclass of process expressions where in the scope of a recursion construct only prefixing, independent parallel composition and guarded choice is allowed; but always yields finite S/T-nets. The two approaches are identical for recursion-free process expressions; in general they agree up to fully concurrent bisimulation equivalence. Here I extend the latter approach to deal with unguarded recursion. I also show that for every finite S/T-net there exists a process expression in the mentioned subclass whose semantics, up to fully concurrent bisimulation, is that net. Moreover, every finite safe flow net is denoted up to event-structure isomorphism by a recursion-free process expression.
Original languageEnglish
Title of host publicationInformation Systems as Reactive Systems (Dagstuhl Seminar 98071)
EditorsHans-Dieter Ehrich, Ursula Goltz, José Meseguer
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages1
Publication statusPublished - 11 Aug 1998
EventInformation Systems as Reactive Systems Workshop, 1998 -
Duration: 11 Aug 199811 Aug 1998


WorkshopInformation Systems as Reactive Systems Workshop, 1998


Dive into the research topics of 'On the Relative Expressiveness of Petri Nets, Event Structures and Process Algebras abstract)'. Together they form a unique fingerprint.

Cite this