Affiliations: Department of Computer Science, University of Surrey, Guildford, Surrey GU2 5XH, England. e-mail address: [email protected]
Note: [] Address for correspondence: Department of Computer Science, University of Surrey, Guildford, Surrey GU2 5XH, England
Abstract: In this paper, we consider two formal semantics for path programs. The first is a version of the net semantics introduced in [8] and further described in [7], and the second is an extension of the vector semantics of [15]. The extension involves the idea of tagging vectors with sets of sets of action names as with acceptance sets [3, 5] or refusal sets [1, 6] as used in the semantics of certain process algebras. The net semantics of [8, 7] associates a path program with an isomorphism class of labelled, marked nets - two such nets being isomorphic if they have identical pictorial representations and consequently describe the same system. A behaviour of such a class is an isomorphism class of cycle-free labeled nets showing the (partial) order in which conditions have held and events have occurred. We review these basic ideas and then present a version of the [7] semantics. We next present an acceptance vector semantics for path programs. An acceptance vector consists of a collection of sequences, one for each component path, describing the sequence of actions associated with the path in question during some period of activity, together with a set of actions which are available to continue the behaviour represented by the collection. Finally, we show that the two semantics are related in the sense that every net based behaviour may be transformed into an accceptance vector.
Keywords: Path Expressions, Petri Nets, Concurrency, Vector Languages, Acceptance Sets
