TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Constructing Minimal Coverability Sets

Tutkimustuotosvertaisarvioitu

Standard

Constructing Minimal Coverability Sets. / Piipponen, Artturi; Valmari, Antti.

julkaisussa: Fundamenta Informaticae, Vuosikerta 143, Nro 3-4, 04.03.2016, s. 393-414.

Tutkimustuotosvertaisarvioitu

Harvard

Piipponen, A & Valmari, A 2016, 'Constructing Minimal Coverability Sets', Fundamenta Informaticae, Vuosikerta. 143, Nro 3-4, Sivut 393-414. https://doi.org/10.3233/FI-2016-1319

APA

Piipponen, A., & Valmari, A. (2016). Constructing Minimal Coverability Sets. Fundamenta Informaticae, 143(3-4), 393-414. https://doi.org/10.3233/FI-2016-1319

Vancouver

Piipponen A, Valmari A. Constructing Minimal Coverability Sets. Fundamenta Informaticae. 2016 maalis 4;143(3-4):393-414. https://doi.org/10.3233/FI-2016-1319

Author

Piipponen, Artturi ; Valmari, Antti. / Constructing Minimal Coverability Sets. Julkaisussa: Fundamenta Informaticae. 2016 ; Vuosikerta 143, Nro 3-4. Sivut 393-414.

Bibtex - Lataa

@article{0c1109a788de458bab194bf5c8706547,
title = "Constructing Minimal Coverability Sets",
abstract = "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.",
keywords = "antichain data structure, coverability set, Tarjan's algorithm",
author = "Artturi Piipponen and Antti Valmari",
year = "2016",
month = "3",
day = "4",
doi = "10.3233/FI-2016-1319",
language = "English",
volume = "143",
pages = "393--414",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "3-4",

}

RIS (suitable for import to EndNote) - Lataa

TY - JOUR

T1 - Constructing Minimal Coverability Sets

AU - Piipponen, Artturi

AU - Valmari, Antti

PY - 2016/3/4

Y1 - 2016/3/4

N2 - 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.

AB - 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.

KW - antichain data structure

KW - coverability set

KW - Tarjan's algorithm

U2 - 10.3233/FI-2016-1319

DO - 10.3233/FI-2016-1319

M3 - Article

VL - 143

SP - 393

EP - 414

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 3-4

ER -