Optimising enabling tests and unfoldings of algebraic system nets

Reference:

Marko Mäkelä. Optimising enabling tests and unfoldings of algebraic system nets. In José-Manuel Colom and Maciej Koutny, editors, Application and Theory of Petri Nets 2001: 22^nd International Conference, ICATPN 2001, number 2075 in Lecture Notes in Computer Science, pages 283–302, Newcastle upon Tyne, UK, June 2001. Springer-Verlag, Berlin, Germany.

Abstract:

Reachability analysis and simulation tools for high-level nets spend a significant amount of the computing time in performing enabling tests, determining the assignments under which transitions are enabled. Unlike the majority of earlier work on computing enabled transition bindings, the techniques presented in this paper are highly independent of the algebraic operations supported by the high-level net formalism. Performing enabling tests is viewed as a unification problem. A unification algorithm is presented and modifications to it are suggested. One variant of the algorithm constructs finite unfoldings for nets with unbounded domains. Some heuristics for optimising the enabling tests are discussed and their usefulness is evaluated based on experiments. The algorithms have been implemented in the reachability analyser Maria.

Keywords:

high-level Petri nets, reachability analysis, unification, unfolding

Suggested BibTeX entry:

@inproceedings{MakelaMarko-Makela:enabling,
    address = {Newcastle upon Tyne, UK},
    author = {Marko M{\"a}kel{\"a}},
    booktitle = {Application and Theory of Petri Nets 2001: 22\textsuperscript{nd} International Conference, ICATPN 2001},
    editor = {José-Manuel Colom and Maciej Koutny},
    month = {June},
    number = {2075},
    pages = {283--302},
    publisher = {Springer-Verlag, Berlin, Germany},
    series = {Lecture Notes in Computer Science},
    title = {Optimising enabling tests and unfoldings of algebraic system nets},
    year = {2001},
}