{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,17]],"date-time":"2026-10-17T16:23:38Z","timestamp":1792254218212,"version":"4.4.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,30]],"date-time":"2017-04-30T00:00:00Z","timestamp":1493510400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds.<\/jats:p>","DOI":"10.1145\/3060139","type":"journal-article","created":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T19:32:40Z","timestamp":1496259160000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Faster Statistical Model Checking for Unbounded Temporal Properties"],"prefix":"10.1145","volume":"18","author":[{"given":"Przemys\u0142aw","family":"Daca","sequence":"first","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas A.","family":"Henzinger","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"K\u0159et\u00ednsk\u00fd","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tatjana","family":"Petrov","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,5,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Principles of Model Checking","author":"Baier Christel","unstructured":"Christel Baier and Joost-Pieter Katoen . 2008. Principles of Model Checking . MIT Press . Christel Baier and Joost-Pieter Katoen. 2008. Principles of Model Checking. MIT Press."},{"key":"e_1_2_1_2_1","series-title":"Mathematical Statistics: Basic Ideas and Selected Topics","volume-title":"Mathematical Statistics: Basic Ideas and Selected Topics. Number","author":"Bickel P. J.","year":"2000","unstructured":"P. J. Bickel and K. A. Doksum . 2000 . Mathematical Statistics: Basic Ideas and Selected Topics. Number Bd. 1 in Mathematical Statistics: Basic Ideas and Selected Topics . Prentice Hall . P. J. Bickel and K. A. Doksum. 2000. Mathematical Statistics: Basic Ideas and Selected Topics. Number Bd. 1 in Mathematical Statistics: Basic Ideas and Selected Topics. Prentice Hall."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11936-6_8"},{"key":"e_1_2_1_4_1","volume-title":"Marius Mikucionis, Danny B\u00f8gsted Poulsen, Axel Legay, and Zheng Wang.","author":"Bulychev Peter E.","year":"2012","unstructured":"Peter E. Bulychev , Alexandre David , Kim Guldstrand Larsen , Marius Mikucionis, Danny B\u00f8gsted Poulsen, Axel Legay, and Zheng Wang. 2012 . UPPAAL-SMC: Statistical model checking for priced timed automata. In QAPL. 1--16. Peter E. Bulychev, Alexandre David, Kim Guldstrand Larsen, Marius Mikucionis, Danny B\u00f8gsted Poulsen, Axel Legay, and Zheng Wang. 2012. UPPAAL-SMC: Statistical model checking for priced timed automata. In QAPL. 1--16."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28729-9_18"},{"key":"e_1_2_1_6_1","unstructured":"Przemys\u0142aw Daca. 2016. Tool for the paper. (2016). http:\/\/pub.ist.ac.at\/&sim;przemek\/pa_tool.html.  Przemys\u0142aw Daca. 2016. Tool for the paper. (2016). http:\/\/pub.ist.ac.at\/&sim;przemek\/pa_tool.html."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49674-9_7"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 27th International Conference on Concurrency Theory (CONCUR\u201916)","volume":"59","author":"Daca Przemyslaw","year":"2016","unstructured":"Przemyslaw Daca , Thomas A. Henzinger , Jan Kret\u00ednsk\u00fd , and Tatjana Petrov . 2016 b. Linear distances between Markov chains . In Proceedings of the 27th International Conference on Concurrency Theory (CONCUR\u201916) , Jos\u00e9e Desharnais and Radha Jagadeesan (Eds.) , Vol. 59 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 20:1--20:15. Przemyslaw Daca, Thomas A. Henzinger, Jan Kret\u00ednsk\u00fd, and Tatjana Petrov. 2016b. Linear distances between Markov chains. In Proceedings of the 27th International Conference on Concurrency Theory (CONCUR\u201916), Jos\u00e9e Desharnais and Radha Jagadeesan (Eds.), Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 20:1--20:15."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-014-0361-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31980-1_18"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1858996.1859043"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Thomas H\u00e9rault Richard Lassaigne Fr\u00e9d\u00e9ric Magniette and Sylvain Peyronnet. 2004. Approximate probabilistic model checking. In VMCAI. 73--84.  Thomas H\u00e9rault Richard Lassaigne Fr\u00e9d\u00e9ric Magniette and Sylvain Peyronnet. 2004. Approximate probabilistic model checking. In VMCAI. 73--84.","DOI":"10.1007\/978-3-540-24622-0_8"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 3rd International Workshop on the Numerical Solution of Markov Chains. Citeseer, 188--207","author":"Hermanns Holger","year":"1999","unstructured":"Holger Hermanns , Joachim Meyer-Kayser , and Markus Siegle . 1999 . Multi terminal binary decision diagrams to represent and analyse continuous time Markov chains . In Proceedings of the 3rd International Workshop on the Numerical Solution of Markov Chains. Citeseer, 188--207 . Holger Hermanns, Joachim Meyer-Kayser, and Markus Siegle. 1999. Multi terminal binary decision diagrams to represent and analyse continuous time Markov chains. In Proceedings of the 3rd International Workshop on the Numerical Solution of Markov Chains. Citeseer, 188--207."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28756-5_37"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03845-7_15"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Marta Z. Kwiatkowska Gethin Norman and David Parker. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In CAV. 585--591.   Marta Z. Kwiatkowska Gethin Norman and David Parker. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In CAV. 585--591.","DOI":"10.1007\/978-3-642-22110-1_47"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2012.14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2007.11.006"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"James R. Norris. 1998. Markov Chains. Cambridge University Press.  James R. Norris. 1998. Markov Chains. Cambridge University Press.","DOI":"10.1017\/CBO9780511810633"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Johan Oudinet Alain Denise Marie-Claude Gaudel Richard Lassaigne and Sylvain Peyronnet. 2011. Uniform Monte-Carlo model checking. In FASE. 127--140.   Johan Oudinet Alain Denise Marie-Claude Gaudel Richard Lassaigne and Sylvain Peyronnet. 2011. Uniform Monte-Carlo model checking. In FASE. 127--140.","DOI":"10.1007\/978-3-642-19811-3_10"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.32"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04761-9_11"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Koushik Sen Mahesh Viswanathan and Gul Agha. 2004. Statistical model checking of black-box probabilistic systems. In CAV. 202--215.  Koushik Sen Mahesh Viswanathan and Gul Agha. 2004. Statistical model checking of black-box probabilistic systems. In CAV. 202--215.","DOI":"10.1007\/978-3-540-27813-9_16"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_26"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOTP.0000011995.28536.ef"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731118"},{"key":"e_1_2_1_27_1","unstructured":"H\u00e5kan L. S. Younes. 2004. Planning and verification for stochastic processes with asynchronous events. In AAAI. 1001--1002.   H\u00e5kan L. S. Younes. 2004. Planning and verification for stochastic processes with asynchronous events. In AAAI. 1001--1002."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"H\u00e5kan L. S. Younes Edmund M. Clarke and Paolo Zuliani. 2010. Statistical verification of probabilistic properties with unbounded until. In SBMF. 144--160.   H\u00e5kan L. S. Younes Edmund M. Clarke and Paolo Zuliani. 2010. Statistical verification of probabilistic properties with unbounded until. In SBMF. 144--160.","DOI":"10.1007\/978-3-642-19829-8_10"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-005-0187-8"},{"key":"e_1_2_1_30_1","volume-title":"Simmons","author":"Younes H\u00e5kan L. S.","year":"2002","unstructured":"H\u00e5kan L. S. Younes and Reid G . Simmons . 2002 . Probabilistic verification of discrete event systems using acceptance sampling. In CAV. Springer , 223--235. H\u00e5kan L. S. Younes and Reid G. Simmons. 2002. Probabilistic verification of discrete event systems using acceptance sampling. In CAV. Springer, 223--235."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.05.002"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3060139","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3060139","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:19Z","timestamp":1750215799000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3060139"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,30]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3060139"],"URL":"https:\/\/doi.org\/10.1145\/3060139","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,30]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}