BOENNELAND, Frederik M., Peter G. JENSEN, Kim G. LARSEN, Marco MUNIZ and Jiří SRBA. Start Pruning When Time Gets Urgent: Partial Order Reduction for Timed Systems. In Proceedings of the 30th International Conference on Computer Aided Verification (CAV'18). Netherlands: Springer, 2018, p. 527-546. ISBN 978-3-319-96144-6. Available from: https://dx.doi.org/10.1007/978-3-319-96145-3_28.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Start Pruning When Time Gets Urgent: Partial Order Reduction for Timed Systems
Authors BOENNELAND, Frederik M. (208 Denmark), Peter G. JENSEN (208 Denmark), Kim G. LARSEN (208 Denmark), Marco MUNIZ (604 Peru) and Jiří SRBA (203 Czech Republic, guarantor, belonging to the institution).
Edition Netherlands, Proceedings of the 30th International Conference on Computer Aided Verification (CAV'18), p. 527-546, 20 pp. 2018.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
WWW URL
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/18:00106625
Organization unit Faculty of Informatics
ISBN 978-3-319-96144-6
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-96145-3_28
UT WoS 000491481600028
Keywords in English partial order reduction; timed-arc Petri nets; stubborn sets
Tags core_A, firank_1
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 16/5/2022 14:34.
Abstract
Partial order reduction for timed systems is a challenging topic due to the dependencies among events induced by time acting as a global synchronization mechanism. So far, there has only been a limited success in finding practically applicable solutions yielding significant state space reductions. We suggest a working and efficient method to facilitate stubborn set reduction for timed systems with urgent behaviour. We first describe the framework in the general setting of timed labelled transition systems and then instantiate it to the case of timed-arc Petri nets. The basic idea is that we can employ classical untimed partial order reduction techniques as long as urgent behaviour is enforced. Our solution is implemented in the model checker TAPAAL and the feature is now broadly available to the users of the tool. By a series of larger case studies, we document the benefits of our method and its applicability to real-world scenarios.
PrintDisplayed: 27/4/2024 04:27