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
Pages12
Number of pages1
Volume200
DOIs
Publication statusPublished - 11 Aug 1998
EventInformation Systems as Reactive Systems Workshop, 1998 -
Duration: 11 Aug 199811 Aug 1998

Workshop

WorkshopInformation Systems as Reactive Systems Workshop, 1998
Period11/08/9811/08/98

Fingerprint

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