{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:02:48Z","timestamp":1742958168457,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031095733"},{"type":"electronic","value":"9783031095740"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09574-0_9","type":"book-chapter","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:36:07Z","timestamp":1656005767000},"page":"133-151","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Bounds for\u00a0Synchronizing Markov Decision Processes"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Doyen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marie","family":"van den Bogaard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Akshay, S., Genest, B., Vyas, N.: Distribution-based objectives for Markov decision processes. In: Proceedings of LICS, pp. 36\u201345. ACM (2018)","DOI":"10.1145\/3209108.3209185"},{"key":"9_CR2","unstructured":"Baier, C., Katoen, J.-P.: Principles of Model Checking. MIT Press, Cambridge (2008)"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/3-540-45793-3_21","volume-title":"Computer Science Logic","author":"D Beauquier","year":"2002","unstructured":"Beauquier, D., Rabinovich, A., Slissenko, A.: A logic of probability with decidable model-checking. In: Bradfield, J. (ed.) CSL 2002. LNCS, vol. 2471, pp. 306\u2013321. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45793-3_21"},{"key":"9_CR4","unstructured":"Bell, P.C., Semukhin, P.: Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs. In: Proceedings of CONCUR, vol. 171 of LIPIcs, pp. 22:1\u201322:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"9_CR5","unstructured":"Bertrand, N., Dewaskar, M., Genest, B., Gimbert, H.: Controlling a population. In: Proceedings of CONCUR: Concurrency Theory, volume 85 of LIPIcs, pp. 12:1\u201312:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"key":"9_CR6","unstructured":"Chatterjee, K., Doyen, L.: Computation tree logic for synchronization properties. In: Proc. of ICALP: Automata, Languages, and Programming, volume 55 of LIPIcs, pp. 98:1\u201398:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"2","key":"9_CR7","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.jcss.2011.05.002","volume":"78","author":"K Chatterjee","year":"2012","unstructured":"Chatterjee, K., Henzinger, T.A.: A survey of stochastic $$\\omega $$-regular games. J. Comput. Syst. Sci. 78(2), 394\u2013413 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-030-45231-5_7","volume-title":"Foundations of Software Science and Computation Structures","author":"T Colcombet","year":"2020","unstructured":"Colcombet, T., Fijalkow, N., Ohlmann, P.: Controlling a random population. In: FoSSaCS 2020. LNCS, vol. 12077, pp. 119\u2013135. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45231-5_7"},{"issue":"4","key":"9_CR9","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1145\/210332.210339","volume":"42","author":"C Courcoubetis","year":"1995","unstructured":"Courcoubetis, C., Yannakakis, M.: The complexity of probabilistic verification. J. ACM 42(4), 857\u2013907 (1995)","journal-title":"J. ACM"},{"key":"9_CR10","unstructured":"de Alfaro, L.: Formal verification of probabilistic systems. Ph.D. thesis, Stanford University (1997)"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"de Alfaro, L., Henzinger, T.A.: Concurrent omega-regular games. In: Proceedings. of LICS: Logic in Computer Science, pp. 141\u2013154. IEEE (2000)","DOI":"10.1109\/LICS.2000.855763"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jcss.2018.09.004","volume":"100","author":"L Doyen","year":"2019","unstructured":"Doyen, L., Massart, T., Shirmohammadi, M.: The complexity of synchronizing Markov decision processes. J. Comput. Syst. Sci. 100, 96\u2013129 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Doyen, L., van den Bogaard, M.: Bounds for synchronizing Markov decision processes. CoRR, abs\/2204.12814 (2022)","DOI":"10.1007\/978-3-031-09574-0_9"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Feinberg, E., Shwartz, A. (eds.) Handbook of Markov Decision Processes - Methods and Applications. Kluwer, Boston (2002)","DOI":"10.1007\/978-1-4615-0805-2"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Gallager, R.G.: Stochastic Processes: Theory for Applications. Cambridge University Press, New York (2013)","DOI":"10.1017\/CBO9781139626514"},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-662-44584-6_18","volume-title":"CONCUR 2014 \u2013 Concurrency Theory","author":"H Hermanns","year":"2014","unstructured":"Hermanns, H., Kr\u010d\u00e1l, J., K\u0159et\u00ednsk\u00fd, J.: Probabilistic Bisimulation: naturally on distributions. In: Baldan, P., Gorla, D. (eds.) CONCUR 2014. LNCS, vol. 8704, pp. 249\u2013265. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44584-6_18"},{"issue":"5","key":"9_CR17","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.ipl.2007.06.006","volume":"104","author":"P Jancar","year":"2007","unstructured":"Jancar, P., Sawa, Z.: A note on emptiness for alternating finite automata with a one-letter alphabet. Inf. Process. Lett. 104(5), 164\u2013167 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Korthikanti, V.A., Viswanathan, M., Agha, G., Kwon, Y.: Reasoning about MDPs as transformers of probability distributions. In: Proceedings of QEST: Quantitative Evaluation of Systems, pp. 199\u2013208. IEEE Computer Society (2010)","DOI":"10.1109\/QEST.2010.35"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Puterman. M.L.: Markov Decision Processes. John Wiley and Sons, New York (1994)","DOI":"10.1002\/9780470316887"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"MO Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Inf. Control 6, 230\u2013245 (1963)","journal-title":"Inf. Control"},{"key":"9_CR21","unstructured":"Shirmohammadi, M.: Qualitative analysis of probabilistic synchronizing systems. Ph.D. thesis, U. Libre de Bruxelles & \u00c9cole Normale Sup\u00e9rieure de Cachan (2014)"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: Automatic verification of probabilistic concurrent finite-state programs. In: Proceedings of FOCS, pp. 327\u2013338. IEEE Computer Society (1985)","DOI":"10.1109\/SFCS.1985.12"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09574-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T17:17:15Z","timestamp":1727457435000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09574-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031095733","9783031095740"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09574-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. Petersburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2022\/","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":"51","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":"21","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":"41% - 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":"7","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)"}}]}}