{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:04Z","timestamp":1750307704114,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0429639CCF-0448178CCF-0742686CCF-0509321"],"award-info":[{"award-number":["CCF-0429639CCF-0448178CCF-0742686CCF-0509321"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            In this article, we introduce the model of\n            <jats:italic>finite state probabilistic monitors<\/jats:italic>\n            (FPM), which are finite state automata on infinite strings that have probabilistic transitions and an absorbing reject state. FPMs are a natural automata model that can be seen as either randomized run-time monitoring algorithms or as models of open, probabilistic reactive systems that can fail. We give a number of results that characterize, topologically as well as with respect to their computational power, the sets of languages recognized by FPMs. We also study the emptiness and universality problems for such automata and give exact complexity bounds for these problems.\n          <\/jats:p>","DOI":"10.1145\/1552285.1552287","type":"journal-article","created":{"date-parts":[[2009,8,24]],"date-time":"2009-08-24T14:08:31Z","timestamp":1251122911000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["On the expressiveness and complexity of randomization in finite state monitors"],"prefix":"10.1145","volume":"56","author":[{"given":"Rohit","family":"Chadha","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana-Champaign,Illinois"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. Prasad","family":"Sistla","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago, Chicago, Illinois"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana-Champaign,Illinois"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,8,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90056-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_36"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures","author":"Baier C.","unstructured":"Baier , C. , Bertrand , N. , and Gr &amp;#246;&amp;#223;er, M. 2008. On decision problems for probabilistic B&amp;#252;chi automata . In Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures . Lecture Notes in Computer Science . Springer-Verlag , Berlin, Germany (FoSSaCS). 287--301. Baier, C., Bertrand, N., and Gr&amp;#246;&amp;#223;er, M. 2008. On decision problems for probabilistic B&amp;#252;chi automata. In Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany (FoSSaCS). 287--301."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.41"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944836_25"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.42"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297069"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63519"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.368136"},{"volume-title":"Proceeding of the Mathematical Foundations of Computer Science","author":"Freivalds R.","key":"e_1_2_1_10_1","unstructured":"Freivalds , R. 1981. Probabilistic two-way machines . In Proceeding of the Mathematical Foundations of Computer Science . Springer-Verlag , Berlin, Germany , 33--45. Freivalds, R. 1981. Probabilistic two-way machines. In Proceeding of the Mathematical Foundations of Computer Science. Springer-Verlag, Berlin, Germany, 33--45."},{"key":"e_1_2_1_11_1","volume-title":"Dynamics: Comprehensive support for runtime monitoring. In Runtime Verification","author":"Gates A.","year":"2001","unstructured":"Gates , A. , and Roach , S . 2001 . Dynamics: Comprehensive support for runtime monitoring. In Runtime Verification . ENTCS. Elsevier Publishing , Amsterdam, The Netherlands. Gates, A., and Roach, S. 2001. Dynamics: Comprehensive support for runtime monitoring. In Runtime Verification. ENTCS. Elsevier Publishing, Amsterdam, The Netherlands."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-93900-9_12"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111596.1111601"},{"key":"e_1_2_1_14_1","unstructured":"Havelund K. and Rosu G. 2001. Monitoring java programs with JavaPathExplorer. In Runtime Verification. ENTCS. Elsevier Publishing Amesterdam The Netherlands.  Havelund K. and Rosu G. 2001. Monitoring java programs with JavaPathExplorer. In Runtime Verification. ENTCS. Elsevier Publishing Amesterdam The Netherlands."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/277631.277644"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Kemeny J. and Snell J. 1976. Denumerable Markov Chains. Springer-Verlag Berlin Germany.  Kemeny J. and Snell J. 1976. Denumerable Markov Chains. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-1-4684-9455-6"},{"volume-title":"Proceedings of the IEEE Euromicro Conference on Real-time Systems. IEEE Computer Society Press, Los Alamitos, 114--122","author":"Kim M.","key":"e_1_2_1_18_1","unstructured":"Kim , M. , Viswanathan , M., B. - Abdullah , H. , Kannan , S. , Lee , I. , and Sokolsky , O . 1999. Formally specified monitoring of temporal properties . In Proceedings of the IEEE Euromicro Conference on Real-time Systems. IEEE Computer Society Press, Los Alamitos, 114--122 . Kim, M., Viswanathan, M., B.-Abdullah, H., Kannan, S., Lee, I., and Sokolsky, O. 1999. Formally specified monitoring of temporal properties. In Proceedings of the IEEE Euromicro Conference on Real-time Systems. IEEE Computer Society Press, Los Alamitos, 114--122."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Kortenkamp D. Milam T. Simmons R. and Fernandez J. L. 2001. Collecting and analyzing data from distributed control programs. In Runtime Verification. ENTCS. Elsevier Publishing Amesterdam The Netherlands.  Kortenkamp D. Milam T. Simmons R. and Fernandez J. L. 2001. Collecting and analyzing data from distributed control programs. In Runtime Verification. ENTCS. Elsevier Publishing Amesterdam The Netherlands.","DOI":"10.1016\/S1571-0661(04)00255-5"},{"key":"e_1_2_1_20_1","series-title":"Lecture Notes in Computer Science","volume-title":"Logical foundation, distributed systems: Methods and tools for specification","author":"Lamport L.","unstructured":"Lamport , L. 1985. Logical foundation, distributed systems: Methods and tools for specification . Lecture Notes in Computer Science , vol. 190 . Springer-Verlag , Berlin, Germany . Lamport, L. 1985. Logical foundation, distributed systems: Methods and tools for specification. Lecture Notes in Computer Science, vol. 190. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-004-0053-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455526.1455532"},{"key":"e_1_2_1_24_1","unstructured":"Mansouri-Samani M. and Sloman M. 1992. Monitoring distributed systems: A survey. Res. Rep. DOC92\/93 Imperial College London UK.  Mansouri-Samani M. and Sloman M. 1992. Monitoring distributed systems: A survey. Res. Rep. DOC92\/93 Imperial College London UK."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11539452_41"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90353-7"},{"key":"e_1_2_1_27_1","unstructured":"Papoulis A. and Pillai S. U. 2002. Probability Random Variables and Stochastic Processes. McGraw Hill New York.  Papoulis A. and Pillai S. U. 2002. Probability Random Variables and Stochastic Processes. McGraw Hill New York."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/263109.263160"},{"volume-title":"Introduction to Probabilistic Automata","author":"Paz A.","key":"e_1_2_1_29_1","unstructured":"Paz , A. 1971. Introduction to Probabilistic Automata . Academic Press , Orlando . Paz, A. 1971. Introduction to Probabilistic Automata. Academic Press, Orlando."},{"key":"e_1_2_1_30_1","volume-title":"-E","author":"Perrin D.","year":"2004","unstructured":"Perrin , D. , and Pin , J . -E . 2004 . Infinite Words : Automata, Semigroups, Logic and Games. Elseiver, Amesterdam, The Netherlands . Perrin, D., and Pin, J.-E. 2004. Infinite Words: Automata, Semigroups, Logic and Games. Elseiver, Amesterdam, The Netherlands."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/C-M.1981.220255"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11813040_38"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"volume-title":"Proceedings of the Systems Administration Conference. USENIX Association, 1--8.","author":"Ranum M. J.","key":"e_1_2_1_34_1","unstructured":"Ranum , M. J. , Landfield , K. , Stolarchuk , M. , Sienkiewicz , M. , Lambeth , A. , and Wall , E . 1997. Implementing a generalized tool for network monitoring . In Proceedings of the Systems Administration Conference. USENIX Association, 1--8. Ranum, M. J., Landfield, K., Stolarchuk, M., Sienkiewicz, M., Lambeth, A., and Wall, E. 1997. Implementing a generalized tool for network monitoring. In Proceedings of the Systems Administration Conference. USENIX Association, 1--8."},{"key":"e_1_2_1_35_1","unstructured":"Salomaa A. 1973. Formal Languages. Academic Press Orlando.   Salomaa A. 1973. Formal Languages. Academic Press Orlando."},{"volume-title":"Proceedings of the 7th International Workshop on Runtime Verification. Springer-Verlag","author":"Sammapun U.","key":"e_1_2_1_36_1","unstructured":"Sammapun , U. , Lee , I. , Sokolsky , O. , and Regehr , J . 2007. Statistical runtime checking of probabilistic properties . In Proceedings of the 7th International Workshop on Runtime Verification. Springer-Verlag , Berlin, Germany, 164--175. Sammapun, U., Lee, I., Sokolsky, O., and Regehr, J. 2007. Statistical runtime checking of probabilistic properties. In Proceedings of the 7th International Workshop on Runtime Verification. Springer-Verlag, Berlin, Germany, 164--175."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/353323.353382"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.386988"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/323596.323600"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of International Conference on Verification, Model Checking and Abstract Interpretation. Lecture Notes in Computer Science","volume":"4905","author":"Sistla A. P.","unstructured":"Sistla , A. P. , and Srinivas , A. R . 2008. Monitoring temporal properties of stochastic systems . In Proceedings of International Conference on Verification, Model Checking and Abstract Interpretation. Lecture Notes in Computer Science , vol. 4905 . Springer-Verlag, Berlin, Germany, 294--308. Sistla, A. P., and Srinivas, A. R. 2008. Monitoring temporal properties of stochastic systems. In Proceedings of International Conference on Verification, Model Checking and Abstract Interpretation. Lecture Notes in Computer Science, vol. 4905. Springer-Verlag, Berlin, Germany, 294--308."},{"key":"e_1_2_1_41_1","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepcsenyi R.","year":"1987","unstructured":"Szelepcsenyi , R. 1987 . The method of forcing for nondeterministic automata . Bull. EATCS 33 , 96 -- 100 . Szelepcsenyi, R. 1987. The method of forcing for nondeterministic automata. Bull. EATCS 33, 96--100.","journal-title":"Bull. EATCS"},{"volume-title":"Handbook of Theoretical Computer Science.","author":"Thomas W.","key":"e_1_2_1_42_1","unstructured":"Thomas , W. 1990. Automata on infinite objects . In Handbook of Theoretical Computer Science. vol. B. Elsevier, Amsterdam, The Netherlands, 133-- 192 . Thomas, W. 1990. Automata on infinite objects. In Handbook of Theoretical Computer Science. vol. B. Elsevier, Amsterdam, The Netherlands, 133--192."},{"key":"e_1_2_1_43_1","unstructured":"Time Rover. 1997. http:\/\/www.time-rover.com.  Time Rover. 1997. http:\/\/www.time-rover.com."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.12"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1552285.1552287","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1552285.1552287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:04Z","timestamp":1750253404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1552285.1552287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1145\/1552285.1552287"],"URL":"https:\/\/doi.org\/10.1145\/1552285.1552287","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,8]]},"assertion":[{"value":"2008-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}