Depth-First Net Unfoldings and Equivalent Reduction
In Petri net unfolding, according to the strategies of breadth first and depth first, the biggest problem lies in the potential explosion of the state space. Unfolding generates either accessible trees or branch processes. Making marking reduction or branch cutting accessible proves to be an effecti...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-09-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/15/9/1775 |
| _version_ | 1797576530950356992 |
|---|---|
| author | Xu Yang Chen Ye Yijun Chen |
| author_facet | Xu Yang Chen Ye Yijun Chen |
| author_sort | Xu Yang |
| collection | DOAJ |
| description | In Petri net unfolding, according to the strategies of breadth first and depth first, the biggest problem lies in the potential explosion of the state space. Unfolding generates either accessible trees or branch processes. Making marking reduction or branch cutting accessible proves to be an effective approach to mitigating the state space expansion. In this paper, we propose three reduction rules based on similarity equivalence, conduct state space reduction, present three theorems supported by a case study, and propose a new unfolding algorithm for the unfolding process. In both the new case and the experiments, the completeness, optimality, completeness, and memory and time consumption are reduced by about 60%. |
| first_indexed | 2024-03-10T21:54:23Z |
| format | Article |
| id | doaj.art-3da3996559ed4639a1d1a6c5f4c0be9d |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T21:54:23Z |
| publishDate | 2023-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-3da3996559ed4639a1d1a6c5f4c0be9d2023-11-19T13:12:30ZengMDPI AGSymmetry2073-89942023-09-01159177510.3390/sym15091775Depth-First Net Unfoldings and Equivalent ReductionXu Yang0Chen Ye1Yijun Chen2Department of Computer Science and Technology, College of Electronic and Information, Tongji University, Shanghai 201804, ChinaThe Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 201804, ChinaNational Maglev Transportation Engineering R&D Center, Tongji University, Shanghai 201804, ChinaIn Petri net unfolding, according to the strategies of breadth first and depth first, the biggest problem lies in the potential explosion of the state space. Unfolding generates either accessible trees or branch processes. Making marking reduction or branch cutting accessible proves to be an effective approach to mitigating the state space expansion. In this paper, we propose three reduction rules based on similarity equivalence, conduct state space reduction, present three theorems supported by a case study, and propose a new unfolding algorithm for the unfolding process. In both the new case and the experiments, the completeness, optimality, completeness, and memory and time consumption are reduced by about 60%.https://www.mdpi.com/2073-8994/15/9/1775Petri netunfoldingpartial order reductiondepth firstbread first |
| spellingShingle | Xu Yang Chen Ye Yijun Chen Depth-First Net Unfoldings and Equivalent Reduction Symmetry Petri net unfolding partial order reduction depth first bread first |
| title | Depth-First Net Unfoldings and Equivalent Reduction |
| title_full | Depth-First Net Unfoldings and Equivalent Reduction |
| title_fullStr | Depth-First Net Unfoldings and Equivalent Reduction |
| title_full_unstemmed | Depth-First Net Unfoldings and Equivalent Reduction |
| title_short | Depth-First Net Unfoldings and Equivalent Reduction |
| title_sort | depth first net unfoldings and equivalent reduction |
| topic | Petri net unfolding partial order reduction depth first bread first |
| url | https://www.mdpi.com/2073-8994/15/9/1775 |
| work_keys_str_mv | AT xuyang depthfirstnetunfoldingsandequivalentreduction AT chenye depthfirstnetunfoldingsandequivalentreduction AT yijunchen depthfirstnetunfoldingsandequivalentreduction |