Analysis and Synthesis of Net Structures and Transition Graphs

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

Article type: Research Article

Authors: Czaja, Ludwik | Kudlek, Manfred

Affiliations: Warsaw University Banacha 2, 02-097 Warsaw, Poland. lczaja@mimuw.edu.pl | Department Informatik, MIN-Fakultät, Universität Hamburg, Vogt-Kölln-Straße 30. D-22527 Hamburg, Germany. kudlek@informatik.uni-hamburg.de

Note: [] Address for correspondence: Warsaw University, Banacha 2, 02-097 Warsaw, Poland

Abstract: We investigate relations between transition graphs and net structures. Whereas for a given net structure there always exists a reachability graph, the inverse problem to find a net structure for a given transition graph is not solvable in general. We present sufficient and necessary conditions for several classes of transition graphs such as general, pseudo-bounded, bounded and elementary transition graphs, corresponding to general and (pseudo-)bounded P/T nets or C/E nets. We also give maximal and minimal solutions within an algebraic structure of net structures. The entire investigation is formulated in the framework of multiset theory.

DOI: 10.3233/FI-2009-0090

Journal: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 97-110, 2009