TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Constructing Minimal Coverability Sets

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut393-414
Sivumäärä22
JulkaisuFundamenta Informaticae
Vuosikerta143
Numero3-4
DOI - pysyväislinkit
TilaJulkaistu - 4 maaliskuuta 2016
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

This publication addresses two bottlenecks in the construction of minimal coverability sets of Petri nets: the detection of situations where the marking of a place can be converted to ω, and the manipulation of the set A of maximal ω-markings that have been found so far. For the former, a technique is presented that consumes very little time in addition to what maintaining A consumes. It is based on Tarjan's algorithm for detecting maximal strongly connected components of a directed graph. For the latter, a data structure is introduced that resembles BDDs and Covering Sharing Trees, but has additional heuristics designed for the present use. Results from a few experiments are shown. They demonstrate significant savings in running time and varying savings in memory consumption compared to an earlier state-of-the-art technique.

Latausten tilastot

Ei tietoja saatavilla