TY - GEN
T1 - True state-space complexity prediction
T2 - 2009 International Conference on Innovations in Information Technology, IIT '09
AU - Lazarova-Molnar, Sanja
PY - 2009/12/1
Y1 - 2009/12/1
N2 - All state-space based simulation methods are doomed by the phenomenon of state-space explosion. The condition occurs when the simulation becomes memory-infeasible as simulation time advances due to the large number of states in the model. However, state-space explosion is not something that depends solely on the number of discrete states of the model as typically observed. While this is correct and completely sufficient for Markovian models, it is certainly not a sufficient criterion when models involve non-exponential probability distribution functions. In this paper we discuss the phenomenon of state-space explosion in terms of accurate complexity prediction for a general class of models. Its early diagnosis is especially significant in the case of proxel-based simulation, as it can lead towards hybridization of the method by employing discrete phase approximations for the critical states and transitions. This can significantly reduce the computational complexity of the simulation.
AB - All state-space based simulation methods are doomed by the phenomenon of state-space explosion. The condition occurs when the simulation becomes memory-infeasible as simulation time advances due to the large number of states in the model. However, state-space explosion is not something that depends solely on the number of discrete states of the model as typically observed. While this is correct and completely sufficient for Markovian models, it is certainly not a sufficient criterion when models involve non-exponential probability distribution functions. In this paper we discuss the phenomenon of state-space explosion in terms of accurate complexity prediction for a general class of models. Its early diagnosis is especially significant in the case of proxel-based simulation, as it can lead towards hybridization of the method by employing discrete phase approximations for the critical states and transitions. This can significantly reduce the computational complexity of the simulation.
UR - http://www.scopus.com/inward/record.url?scp=77952500874&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952500874&partnerID=8YFLogxK
U2 - 10.1109/IIT.2009.5413761
DO - 10.1109/IIT.2009.5413761
M3 - Conference contribution
AN - SCOPUS:77952500874
SN - 9781424456987
T3 - 2009 International Conference on Innovations in Information Technology, IIT '09
SP - 130
EP - 134
BT - 2009 International Conference on Innovations in Information Technology, IIT '09
Y2 - 15 December 2009 through 17 December 2009
ER -