pax

The aim of this work is to conduct research into synergies between Petri-net theory and reverse engineering. The existence of such synergies is not obvious because each sector is based on different assumptions. These differences relate to two modelling paradigms: clustering and folding. Clustering merges neighboured nodes and corresponds to the construction of complex systems from subsystems. It is widely used in software engineering and in practical applications of Petri nets. Foldings only merge transitions with transitions, places with places and arcs with arcs. They group similar functionality. Hence they preserve behaviour, allow the transfer of semantics and provide deep theoretical insights by means of far-reaching connections to other models of concurrency. A folding-based Petri-net algorithm for reverse engineering is introduced. It recovers a coloured net from an unstructured flat Petri net. The two nets are connected by a folding which amounts to a compact specification of the source net. The algorithm is both flexible and scalable, and this work shows how application heuristics can be integrated into it. Its cost is almost linear with respect to the size of the input net, which is remarkable in the field of reverse engineering. Petri nets may serve as an intuitive model of the interplay of the structural, functional and dynamic aspects of a system. Various methods of modelling aspects apart from concurrency by Petri nets represent an innovation. With such a translation, the algorithm may also analyse legacy systems outside the realms of Petri nets. The result is a novel and powerful method of reverse engineering. A specific example shows how a high-level design may be recovered from low-level implementation information. Moreover, the recovered colouring contains a complete specification inclusive of the data model. The reverse engineering part of this work concentrates on folding-based Petri-net methods because they contain new features. On the other hand, clustering-based techniques share many similarities with known methods. For best results, however, clustering and folding should be appropriately combined. The foundations for such combinations are laid down in the first part of this thesis. Many Petri-net classes known from the literature may be grouped into folding-based and clustering-based types. However, no well-defined link exists between them which would allow the strengths of both approaches to be combined, especially for practical applications. Such a link is presented here in the form of an adjunction, which is a strong two-way relationship taken from category theory. It links folding-based and clustering-based categories. It is shown that these categories have properties typical of folding-based and clustering-based Petri-nets respectively. Further compatible adjunctions express the Petri-net dichotomy of structure and behaviour. To the best of the author's knowledge, this basic principle of Petri-net theory has not yet been formulated categorically. For practical applications, it is important that these concepts can be integrated fairly easily with existing Petri-net tools. This will enrich them with the power of a categorical machinery, e.g. with morphisms, universal constructions and the transfer of behaviour. Coloured nets are simply defined as special comma categories, i.e. essentially folding morphisms. The reduction algorithm introduced here is a proof of the practical value of this approach: it is an iteration of couniversal constructions and the reduction itself has couniversal properties.

Petri nets for reverse engineering

Petri nets for reverse engineering

actions