TY - GEN
T1 - Building correct simulation models is difficult
AU - Yucesan, Enver
AU - Jacobson, Sheldon H.
N1 - Publisher Copyright:
© 1992 ACM.
PY - 1992/12/1
Y1 - 1992/12/1
N2 - An application of the theory of computational complexity to the problem of verifying certain structural properties of discrete event simulation models is illustrated. Such modeling questions as accessibility of states, ordering of events, ambiguity of model specifications, and execution st,alling are asserted to be NP-complete decision problems. These results imply that it is highly unlikely that a polynomial-time algorithm can be devised to verify such properties. The consequences of these assertions cover a wide range of modeling ,and ,an,alysis questions in simulation.
AB - An application of the theory of computational complexity to the problem of verifying certain structural properties of discrete event simulation models is illustrated. Such modeling questions as accessibility of states, ordering of events, ambiguity of model specifications, and execution st,alling are asserted to be NP-complete decision problems. These results imply that it is highly unlikely that a polynomial-time algorithm can be devised to verify such properties. The consequences of these assertions cover a wide range of modeling ,and ,an,alysis questions in simulation.
UR - http://www.scopus.com/inward/record.url?scp=85013571573&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85013571573&partnerID=8YFLogxK
U2 - 10.1145/167293.167720
DO - 10.1145/167293.167720
M3 - Conference contribution
AN - SCOPUS:85013571573
SN - 0780307984
T3 - Proceedings - Winter Simulation Conference
SP - 783
EP - 790
BT - Proceedings of the 24th Conference on Winter Simulation, WSC 1992
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 24th Conference on Winter Simulation, WSC 1992
Y2 - 13 December 1992 through 16 December 1992
ER -