{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T11:34:54Z","timestamp":1743075294635,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030452308"},{"type":"electronic","value":"9783030452315"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Probabilistic B\u00fcchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this work we extend the known classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-automata. Furthermore, we investigate the expressivity of the not yet considered but natural class of weak PBA, and we also show that the regularity problem for weak PBA is undecidable.<\/jats:p>","DOI":"10.1007\/978-3-030-45231-5_27","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"522-541","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ambiguity, Weakness, and Regularity in Probabilistic B\u00fcchi Automata"],"prefix":"10.1007","author":[{"given":"Christof","family":"L\u00f6ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5077-7497","authenticated-orcid":false,"given":"Anton","family":"Pirogov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Baier, C., Bertrand, N., Gr\u00f6\u00dfer, M.: On decision problems for probabilistic b\u00fcchi automata. In: Foundations of Software Science and Computational Structures, 11th International Conference, FOSSACS 2008. Lecture Notes in Computer Science, vol.\u00a04962, pp. 287\u2013301. Springer (2008), https:\/\/doi.org\/10.1007\/978-3-540-78499-9","DOI":"10.1007\/978-3-540-78499-9"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Baier, C., Bertrand, N., Gr\u00f6\u00dfer, M.: Probabilistic automata over infinite words: Expressiveness, efficiency, and decidability. In: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, DCFS 2009. EPTCS, vol.\u00a03, pp. 3\u201316 (2009), https:\/\/doi.org\/10.4204\/EPTCS.3","DOI":"10.4204\/EPTCS.3"},{"key":"27_CR3","unstructured":"Baier, C., Gr\u00f6\u00dfer, M.: Recognizing omega-regular languages with probabilistic automata. In: 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings. pp. 137\u2013146 (2005)"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Baier, C., Gr\u00f6\u00dfer, M., Bertrand, N.: Probabilistic $$\\omega $$-automata. Journal of the ACM (JACM) 59(1), \u00a01 (2012)","DOI":"10.1145\/2108242.2108243"},{"key":"27_CR5","unstructured":"Baier, C., Katoen, J.: Principles of model checking. MIT Press (2008)"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Boigelot, B., Jodogne, S., Wolper, P.: An effective decision procedure for linear arithmetic over the integers and reals. ACM Trans. Comput. Log. 6(3), 614\u2013633 (2005), https:\/\/doi.org\/10.1145\/1071596.1071601","DOI":"10.1145\/1071596.1071601"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Studies in Logic and the Foundations of Mathematics, vol.\u00a044, pp. 1\u201311. Elsevier (1966)","DOI":"10.1016\/S0049-237X(09)70564-6"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Chadha, R., Sistla, A.P., Viswanathan, M.: Power of randomization in automata on infinite strings. Logical Methods in Computer Science 7 (2011)","DOI":"10.2168\/LMCS-7(3:22)2011"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Chadha, R., Sistla, A.P., Viswanathan, M.: Probabilistic B\u00fcchi automata with non-extremal acceptance thresholds. In: International Workshop on Verification, Model Checking, and Abstract Interpretation. pp. 103\u2013117. Springer (2011)","DOI":"10.1007\/978-3-642-18275-4_9"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Chadha, R., Sistla, A.P., Viswanathan, M.: Emptiness under isolation and the value problem for hierarchical probabilistic automata. In: FOSSACS 2017. LNCS, vol. 10203, pp. 231\u2013247 (2017), https:\/\/doi.org\/10.1007\/978-3-662-54458-7","DOI":"10.1007\/978-3-662-54458-7"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Chadha, R., Sistla, A.P., Viswanathan, M., Ben, Y.: Decidable and expressive classes of probabilistic automata. In: FoSSaCS 2015. LNCS, vol.\u00a09034, pp. 200\u2013214. Springer (2015), https:\/\/doi.org\/10.1007\/978-3-662-46678-0","DOI":"10.1007\/978-3-662-46678-0"},{"key":"27_CR12","unstructured":"Fijalkow, N., Riveros, C., Worrell, J.: Probabilistic automata of bounded ambiguity. In: 28th International Conference on Concurrency Theory (CONCUR 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: Decidable and undecidable problems. In: International Colloquium on Automata, Languages, and Programming. pp. 527\u2013538. Springer (2010)","DOI":"10.1007\/978-3-642-14162-1_44"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"Landweber, L.H.: Decision problems for $$\\omega $$-automata. Mathematical Systems Theory 3, 376\u2013384 (1969)","DOI":"10.1007\/BF01691063"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Leroux, J., Sutre, G.: On flatness for 2-dimensional vector addition systems with states. In: International Conference on Concurrency Theory. pp. 402\u2013416. Springer (2004)","DOI":"10.1007\/978-3-540-28644-8_26"},{"key":"27_CR16","unstructured":"L\u00f6ding, C., Pirogov, A.: On finitely ambiguous B\u00fcchi automata. In: Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. pp. 503\u2013515 (2018)"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"L\u00f6ding, C., Thomas, W.: Alternating automata and logics over infinite words. In: Proceedings of the IFIP International Conference on Theoretical Computer Science, IFIP TCS2000. LNCS, vol.\u00a01872, pp. 521\u2013535. Springer (2000)","DOI":"10.1007\/3-540-44929-9_36"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Probabilistic automata. Information and control 6(3), 230\u2013245 (1963)","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Rabinovich, A.: Complementation of finitely ambiguous B\u00fcchi automata. In: Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. pp. 541\u2013552 (2018)","DOI":"10.1007\/978-3-319-98654-8_44"},{"key":"27_CR20","doi-asserted-by":"crossref","unstructured":"Sickert, S., Esparza, J., Jaax, S., K\u0159et\u00ednsk\u00fd, J.: Limit-deterministic B\u00fcchi automata for linear temporal logic. In: Chaudhuri, S., Farzan, A. (eds.) Computer Aided Verification. pp. 312\u2013332. Springer International Publishing, Cham (2016)","DOI":"10.1007\/978-3-319-41540-6_17"},{"key":"27_CR21","doi-asserted-by":"crossref","unstructured":"Sistla, A.P., Vardi, M.Y., Wolper, P.: The complementation problem for B\u00fcchi automata with applications to temporal logic (extended abstract). In: ICALP 1985. LNCS, vol.\u00a0194, pp. 465\u2013474. Springer (1985), https:\/\/doi.org\/10.1007\/BFb0015725","DOI":"10.1007\/BFb0015725"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Staiger, L.: Finite-state $$\\omega $$-languages. Journal of Computer and System Sciences 27(3), 434\u2013448 (1983)","DOI":"10.1016\/0022-0000(83)90051-X"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Automata on infinite objects. In: Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics, pp. 133\u2013192. Elsevier Science Publishers, Amsterdam (1990)","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Language Theory, vol.\u00a0III, pp. 389\u2013455. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theoretical Computer Science 88(2), 325\u2013349 (1991)","DOI":"10.1016\/0304-3975(91)90381-B"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45231-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T13:58:23Z","timestamp":1610027903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45231-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030452308","9783030452315"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45231-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dublin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"98","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference could not take place due to the COVID-19 pandemic. There was an online event on July 2, 2020.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}