BOENNELAND, Frederik M., Peter G. JENSEN, Kim G. LARSEN, Marco MUNIZ and Jiří SRBA. Partial Order Reduction for Reachability Games. Online. In Proceedings of the 30th International Conference on Concurrency Theory (CONCUR'19). Gernmany: Dagstuhl Publishing, 2019, p. 1-15. ISBN 978-3-95977-121-4. Available from: https://dx.doi.org/10.4230/LIPIcs.CONCUR.2019.23.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Partial Order Reduction for Reachability Games
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 Gernmany, Proceedings of the 30th International Conference on Concurrency Theory (CONCUR'19), p. 1-15, 15 pp. 2019.
Publisher Dagstuhl Publishing
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/19:00113643
Organization unit Faculty of Informatics
ISBN 978-3-95977-121-4
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2019.23
Keywords in English partial order reduction; Petri nets; reachability games
Tags core_A, firank_A
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 3/5/2020 13:35.
Abstract
Partial order reductions have been successfully applied to model checking of concurrent systems and practical applications of the technique show nontrivial reduction in the size of the explored state space. We present a theory of partial order reduction based on stubborn sets in the game-theoretical setting of 2-player games with reachability/safety objectives. Our stubborn reduction allows us to prune the interleaving behaviour of both players in the game, and we formally prove its correctness on the class of games played on general labelled transition systems. We then instantiate the framework to the class of weighted Petri net games with inhibitor arcs and provide its efficient implementation in the model checker TAPAAL. Finally, we evaluate our stubborn reduction on several case studies and demonstrate its efficiency.
PrintDisplayed: 23/7/2024 06:29