University of Twente Student Theses
Evaluating Ordering Strategies For State Elimination
Greeuw, P.C.A. de (2025) Evaluating Ordering Strategies For State Elimination.
|
PDF
1MB |
| Abstract: | State elimination is an algorithm which reduces the state space of a Markov chain to a minimum size, without affecting the probabilities, when calculating unbounded reachability properties. The resource consumption in terms of memory and processing is greatly affected by the order in which states are eliminated while the result stays the same. The goal is to identify an order which performs better than other orders before the elimination process starts. This thesis lists several orders for elimination which are present in existing research or implementations. These orders are evaluated against one another on several Markov Chains from other existing research using two metrics. Using the data gathered from this evaluation several novel elimination orders are presented and also evaluated. One of these novel orders, Heuristic2 , has the best result on one metric for eleven out of fourteen models and second best for the remaining three. This result leads to the conclusion that there is one single best elimination order for all models which have been evaluated and likely any other model as well. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 54 computer science |
| Programme: | Computer Science MSc (60300) |
| Link to this item: | https://purl.utwente.nl/essays/106481 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page