{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:57Z","timestamp":1753889817194,"version":"3.41.2"},"reference-count":23,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,9,29]],"date-time":"2011-09-29T00:00:00Z","timestamp":1317254400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"name":"National Science Foundation","award":["0742686"],"award-info":[{"award-number":["0742686"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Probabilistic B\\\"uchi Automata (PBA) are randomized, finite state automata that process input strings of infinite length. Based on the threshold chosen for the acceptance probability, different classes of languages can be defined. In this paper, we present a number of results that clarify the power of such machines and properties of the languages they define. The broad themes we focus on are as follows. We present results on the decidability and precise complexity of the emptiness, universality and language containment problems for such machines, thus answering questions central to the use of these models in formal verification. Next, we characterize the languages recognized by PBAs topologically, demonstrating that though general PBAs can recognize languages that are not regular, topologically the languages are as simple as \\omega-regular languages. Finally, we introduce Hierarchical PBAs, which are syntactically restricted forms of PBAs that are tractable and capture exactly the class of \\omega-regular languages.<\/jats:p>","DOI":"10.2168\/lmcs-7(3:22)2011","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T13:45:24Z","timestamp":1415972724000},"source":"Crossref","is-referenced-by-count":5,"title":["Power of Randomization in Automata on Infinite Strings"],"prefix":"10.46298","volume":"Volume 7, Issue 3","author":[{"given":"Rohit","family":"Chadha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. Prasad","family":"Sistla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2011,9,29]]},"reference":[{"key":"10.2168\/LMCS-7(3:22)2011_AS85","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(85)90056-0","volume":"21","author":"B. Alpern and F. Schneider","year":"1985","journal-title":"Information Processing Letters"},{"key":"10.2168\/LMCS-7(3:22)2011_Baier:fossacs2008","doi-asserted-by":"crossref","unstructured":"C. Baier, N. Bertrand, and M. Gr\u00f6\u00dfer. On decision problems for probabilistic B\u00fcchi automata. In11th International Conference on Foundations of Software Science and Computational Structures, FoSSaCS, pages 287-301, 2008.","DOI":"10.1007\/978-3-540-78499-9_21"},{"key":"10.2168\/LMCS-7(3:22)2011_Baier:lics2005","doi-asserted-by":"crossref","unstructured":"C. Baier and M. Gr\u00f6\u00dfer. Recognizing\u00f8mega-regular languages with probabilistic automata. InProceedings of the IEEE Symposium on Logic in Computer Science, pages 137-146, 2005.","DOI":"10.1109\/LICS.2005.41"},{"key":"10.2168\/LMCS-7(3:22)2011_condon-lipton","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63519"},{"key":"10.2168\/LMCS-7(3:22)2011_rch:sis:mv:08","doi-asserted-by":"crossref","unstructured":"R. Chadha, A. P. Sistla, and M. Viswanathan. On the expressiveness and complexity of randomization in finite state monitors. InLICS 2008- 23rd Annual IEEE Symposium on Logic in Computer Science, pages 18-29. IEEE Computer Society, 2008.","DOI":"10.1109\/LICS.2008.42"},{"key":"10.2168\/LMCS-7(3:22)2011_rch:sis:mv:08a","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552287"},{"key":"10.2168\/LMCS-7(3:22)2011_rch:sis:mv:09","doi-asserted-by":"crossref","unstructured":"R Chadha, A. P. Sistla, and M. Viswanathan. Power of randomization in automata on infinite strings. InProceedings of the 20th International Conference on Concurrency Theory (CONCUR'09), volume 5710 ofLecture Notes in Computer Science, pages 229-243. Springer, 2009.","DOI":"10.1007\/978-3-642-04081-8_16"},{"key":"10.2168\/LMCS-7(3:22)2011_GroesserThesis","unstructured":"M. Gr\u00f6\u00dfer.Reduction Methods for Probabilistic Model Checking. PhD thesis, TU Dresden, 2008."},{"key":"10.2168\/LMCS-7(3:22)2011_hol:pel","doi-asserted-by":"crossref","unstructured":"G. J. Holzmann and D. Peled. The state of spin. InProceedings of the 8th International Conference on Computer Aided Verification, 1996.","DOI":"10.1007\/3-540-61474-5_85"},{"key":"10.2168\/LMCS-7(3:22)2011_markov2","doi-asserted-by":"crossref","unstructured":"J. Kemeny and J. Snell.Denumerable Markov Chains. Springer-Verlag, 1976.","DOI":"10.1007\/978-1-4684-9455-6"},{"key":"10.2168\/LMCS-7(3:22)2011_kur","doi-asserted-by":"crossref","unstructured":"R. P. Kurshan.Computer Aided Verification of the Coordinated Processes: The Automata Theoretic Approach. Princeton University Press, 1994.","DOI":"10.1515\/9781400864041"},{"key":"10.2168\/LMCS-7(3:22)2011_La85","unstructured":"L. Lamport. Logical foundation, distributed systems- methods and tools for specification.Springer-Verlag Lecture Notes in Computer Science, 190, 1985."},{"issue":"4","key":"10.2168\/LMCS-7(3:22)2011_Landweber69","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/BF01691063","volume":"3","author":"L. H. Landweber","year":"1969","journal-title":"Mathematical Systems Theory"},{"key":"10.2168\/LMCS-7(3:22)2011_PAZ","unstructured":"A. Paz.Introduction to Probabilistic Automata. Academic Press, 1971."},{"key":"10.2168\/LMCS-7(3:22)2011_book","unstructured":"D. Perrin and J-E. Pin.Infinite Words: Automata, Semigroups, Logic and Games. Elsevier, 2004."},{"issue":"3","key":"10.2168\/LMCS-7(3:22)2011_Rabin","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M. O. Rabin","year":"1963","journal-title":"Information and Control"},{"key":"10.2168\/LMCS-7(3:22)2011_marta-book","doi-asserted-by":"crossref","unstructured":"J. M. Rutten, M. Kwiatkowska, G. Norman, and D. Parker.Mathematical Techniques for Analyzing Concurrent and Probabilistic Systems. AMS, 2004.","DOI":"10.1090\/crmm\/023"},{"key":"10.2168\/LMCS-7(3:22)2011_SALOMAA","unstructured":"A. Salomaa.Formal Languages. Academic Press, 1973."},{"key":"10.2168\/LMCS-7(3:22)2011_SistlaThesis","unstructured":"A. P. Sistla.Theoretical Issues in the Design and Verification of Distributed Systems. PhD thesis, Harvard University, 1983."},{"key":"10.2168\/LMCS-7(3:22)2011_thomas-handbook","doi-asserted-by":"crossref","unstructured":"W. Thomas. Automata on infinite objects. InHandbook of Theoretical Computer Science, volume B, pages 133-192. 1990.","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"10.2168\/LMCS-7(3:22)2011_markov1","doi-asserted-by":"crossref","unstructured":"M. Vardi. Automatic verification of probabilistic concurrent systems. In26th annual Symposium on Foundations of Computer Science, pages 327-338. IEEE Computer Society Press, 1985.","DOI":"10.1109\/SFCS.1985.12"},{"key":"10.2168\/LMCS-7(3:22)2011_var:wol","unstructured":"M. Vardi and P. Wolper. An automata theoretic approach to automatic program verification. InProceedings of the first IEEE Symposium on Logic in Computer Science, 1986."},{"key":"10.2168\/LMCS-7(3:22)2011_var:wol:sis","doi-asserted-by":"crossref","unstructured":"M. Vardi, P. Wolper, and A. P. Sistla. Reasoning about infinite computation paths. InProceedings of the 24th IEEE Symposium on Foundations of Computer Science, 1983.","DOI":"10.1109\/SFCS.1983.51"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/948\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/948\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:03:36Z","timestamp":1747159416000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/948"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,29]]},"references-count":23,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(3:22)2011","relation":{"references":[{"id-type":"doi","id":"10.1007\/3-540-61474-5_85","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1109.2536","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1109.2536","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2011,9,29]]},"article-number":"948"}}