Reachability in Contextual Nets

Issue title: Concurrency Specification and Programming Workshop (CS&P'2001)

Article type: Research Article

Authors: Winkowski, Józef

Affiliations: Instytut Podstaw Informatyki PAN, Ordona 21, 01-237 Warszawa, Poland

Abstract: Contextual nets, or Petri nets with read arcs, are models of concurrent systems with context dependent actions. The problem of reachability in such nets consists in finding a sequence of transitions that leads from the initial marking of a given contextual net to a given goal marking. The solution to this problem that is presented in this paper consists in constructing a finite complete prefix of the unfolding of the given contextual net, that is a finite prefix in which all the markings that are reachable from the initial marking are present, and in searching in each branch of this prefix for the goal marking by solving an appropriate linear programming problem.

Keywords: contextual net, Petri net with read arcs, contextual occurrence net, branching process, unfolding, configuration, history, cut, narking, state, complete prefix, linear programming

Journal: Fundamenta Informaticae, vol. 51, no. 1-2, pp. 235-250, 2002