Unified Mathematical Framework for Slicing and Symmetry Reduction over Event Structures
Nonclassical slicing and symmetry reduction can act as efficient structural abstract methods for pruning state space when dealing with verification problems. In this paper, we mainly address theoretical and algorithmic aspects for nonclassical slicing and symmetry reduction over prime event structur...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2014/352152 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850173083525054464 |
|---|---|
| author | Xinyan Gao Yingcai Ding Wenbo Liu Kaidi Zheng Siyu Huang Ning Zhou Dakui Li |
| author_facet | Xinyan Gao Yingcai Ding Wenbo Liu Kaidi Zheng Siyu Huang Ning Zhou Dakui Li |
| author_sort | Xinyan Gao |
| collection | DOAJ |
| description | Nonclassical slicing and symmetry reduction can act as efficient structural abstract methods for pruning state space when dealing with verification problems. In this paper, we mainly address theoretical and algorithmic aspects for nonclassical slicing and symmetry reduction over prime event structures. We propose sliced and symmetric quotient reduction models of event structures and present their corresponding algorithms. To construct the underlying foundation of the proposed methodologies, we introduce strong and weak conflict concepts and a pair of mutually inverse operators and extend permutation group based symmetry notion of event structures. We have established a unified mathematical framework for slicing and symmetry reduction, and further investigated the translation, isomorphism, and equivalence relationship and other related basic facts from a theoretical point of view. The framework may provide useful guidance and theoretical exploration for overcoming verification challenges. This paper also demonstrates their practical applications by two cases. |
| format | Article |
| id | doaj-art-d0eb58a2ea41460ebb046ff01aa1139e |
| institution | OA Journals |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-d0eb58a2ea41460ebb046ff01aa1139e2025-08-20T02:19:56ZengWileyJournal of Applied Mathematics1110-757X1687-00422014-01-01201410.1155/2014/352152352152Unified Mathematical Framework for Slicing and Symmetry Reduction over Event StructuresXinyan Gao0Yingcai Ding1Wenbo Liu2Kaidi Zheng3Siyu Huang4Ning Zhou5Dakui Li6G&S Labs, School of Software, Dalian University of Technology, Dalian 116620, ChinaG&S Labs, School of Software, Dalian University of Technology, Dalian 116620, ChinaG&S Labs, School of Software, Dalian University of Technology, Dalian 116620, ChinaG&S Labs, School of Software, Dalian University of Technology, Dalian 116620, ChinaG&S Labs, School of Software, Dalian University of Technology, Dalian 116620, ChinaSchool of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, ChinaG&S Labs, School of Software, Dalian University of Technology, Dalian 116620, ChinaNonclassical slicing and symmetry reduction can act as efficient structural abstract methods for pruning state space when dealing with verification problems. In this paper, we mainly address theoretical and algorithmic aspects for nonclassical slicing and symmetry reduction over prime event structures. We propose sliced and symmetric quotient reduction models of event structures and present their corresponding algorithms. To construct the underlying foundation of the proposed methodologies, we introduce strong and weak conflict concepts and a pair of mutually inverse operators and extend permutation group based symmetry notion of event structures. We have established a unified mathematical framework for slicing and symmetry reduction, and further investigated the translation, isomorphism, and equivalence relationship and other related basic facts from a theoretical point of view. The framework may provide useful guidance and theoretical exploration for overcoming verification challenges. This paper also demonstrates their practical applications by two cases.http://dx.doi.org/10.1155/2014/352152 |
| spellingShingle | Xinyan Gao Yingcai Ding Wenbo Liu Kaidi Zheng Siyu Huang Ning Zhou Dakui Li Unified Mathematical Framework for Slicing and Symmetry Reduction over Event Structures Journal of Applied Mathematics |
| title | Unified Mathematical Framework for Slicing and Symmetry Reduction over Event Structures |
| title_full | Unified Mathematical Framework for Slicing and Symmetry Reduction over Event Structures |
| title_fullStr | Unified Mathematical Framework for Slicing and Symmetry Reduction over Event Structures |
| title_full_unstemmed | Unified Mathematical Framework for Slicing and Symmetry Reduction over Event Structures |
| title_short | Unified Mathematical Framework for Slicing and Symmetry Reduction over Event Structures |
| title_sort | unified mathematical framework for slicing and symmetry reduction over event structures |
| url | http://dx.doi.org/10.1155/2014/352152 |
| work_keys_str_mv | AT xinyangao unifiedmathematicalframeworkforslicingandsymmetryreductionovereventstructures AT yingcaiding unifiedmathematicalframeworkforslicingandsymmetryreductionovereventstructures AT wenboliu unifiedmathematicalframeworkforslicingandsymmetryreductionovereventstructures AT kaidizheng unifiedmathematicalframeworkforslicingandsymmetryreductionovereventstructures AT siyuhuang unifiedmathematicalframeworkforslicingandsymmetryreductionovereventstructures AT ningzhou unifiedmathematicalframeworkforslicingandsymmetryreductionovereventstructures AT dakuili unifiedmathematicalframeworkforslicingandsymmetryreductionovereventstructures |