{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:26:07Z","timestamp":1770279967013,"version":"3.49.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030025076","type":"print"},{"value":"9783030025083","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-02508-3_25","type":"book-chapter","created":{"date-parts":[[2018,10,13]],"date-time":"2018-10-13T14:22:47Z","timestamp":1539440567000},"page":"472-492","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Convex Language Semantics for Nondeterministic\u00a0Probabilistic Automata"],"prefix":"10.1007","author":[{"given":"Gerco","family":"van Heerdt","sequence":"first","affiliation":[]},{"given":"Justin","family":"Hsu","sequence":"additional","affiliation":[]},{"given":"Jo\u00ebl","family":"Ouaknine","sequence":"additional","affiliation":[]},{"given":"Alexandra","family":"Silva","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,15]]},"reference":[{"issue":"2","key":"25_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.ipl.2014.08.013","volume":"115","author":"S Akshay","year":"2015","unstructured":"Akshay, S., Antonopoulos, T., Ouaknine, J., Worrell, J.: Reachability problems for Markov chains. Inf. Process. Lett. 115(2), 155\u2013158 (2015). \n                      https:\/\/doi.org\/10.1016\/j.ipl.2014.08.013","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"25_CR2","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1017\/s0004972700024412","volume":"13","author":"MA Arbib","year":"1975","unstructured":"Arbib, M.A., Manes, E.G.: Fuzzy machines in a category. Bull. Aust. Math. Soc. 13(2), 169\u2013210 (1975). \n                      https:\/\/doi.org\/10.1017\/s0004972700024412","journal-title":"Bull. Aust. Math. Soc."},{"issue":"1\u20132","key":"25_CR3","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10994-013-5408-x","volume":"96","author":"B Balle","year":"2014","unstructured":"Balle, B., Castro, J., Gavald\u00e0, R.: Adaptively learning probabilistic deterministic automata from data streams. Mach. Learn. 96(1\u20132), 99\u2013127 (2014). \n                      https:\/\/doi.org\/10.1007\/s10994-013-5408-x","journal-title":"Mach. Learn."},{"key":"25_CR4","doi-asserted-by":"publisher","unstructured":"Bernardo, M., De Nicola, R., Loreti, M.: Revisiting trace and testing equivalences for nondeterministic and probabilistic processes. Log. Methods Comput. Sci. 10(1), Article no. 16 (2014). \n                      https:\/\/doi.org\/10.2168\/lmcs-10(1:16)2014","DOI":"10.2168\/lmcs-10(1:16)2014"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s00224-003-1061-2","volume":"36","author":"VD Blondel","year":"2003","unstructured":"Blondel, V.D., Canterini, V.: Undecidable problems for probabilistic automata of fixed dimension. Theory Comput. Syst. 36, 231\u2013245 (2003). \n                      https:\/\/doi.org\/10.1007\/s00224-003-1061-2","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"25_CR6","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2713167","volume":"58","author":"F Bonchi","year":"2015","unstructured":"Bonchi, F., Pous, D.: Hacking nondeterminism with induction and coinduction. Commun. ACM 58(2), 87\u201395 (2015). \n                      https:\/\/doi.org\/10.1145\/2713167","journal-title":"Commun. ACM"},{"key":"25_CR7","doi-asserted-by":"publisher","unstructured":"Bonchi, F., Silva, A., Sokolova, A.: The power of convex algebras. In: Meyer, R., Nestmann, U. (eds.) Proceedings of 28th International Conference on Concurrency Theory, CONCUR 2017, Berlin, September 2017. Leibniz International Proceedings in Informatics, vol. 85, Article no. 23. Dagstuhl Publishing, Saarbr\u00fccken\/Wadern (2017). \n                      https:\/\/doi.org\/10.4230\/lipics.concur.2017.23","DOI":"10.4230\/lipics.concur.2017.23"},{"key":"25_CR8","unstructured":"Bonchi, F., Sokolova, A., Vignudelli, V.: Trace semantics for nondeterministic probabilistic automata via determinization. arXiv preprint 1808.00923 (2018). \n                      https:\/\/arxiv.org\/abs\/1808.00923"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-642-04081-8_19","volume-title":"CONCUR 2009 - Concurrency Theory","author":"Y Deng","year":"2009","unstructured":"Deng, Y., van Glabbeek, R.J., Hennessy, M., Morgan, C.: Testing finitary probabilistic processes. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 274\u2013288. Springer, Heidelberg (2009). \n                      https:\/\/doi.org\/10.1007\/978-3-642-04081-8_19"},{"key":"25_CR10","doi-asserted-by":"publisher","unstructured":"Desharnais, J., Edalat, A., Panangaden, P.: A logical characterization of bisimulation for labeled Markov processes. In: Proceedings of 13th Annual IEEE Symposium on Logic in Computer Science. LICS 1998, Indianapolis, IN, June 1998, pp. 478\u2013487. IEEE CS Press, Washington, D.C. (1998). \n                      https:\/\/doi.org\/10.1109\/lics.1998.705681","DOI":"10.1109\/lics.1998.705681"},{"key":"25_CR11","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/104","volume-title":"Recurrence Sequences, Mathematical surveys and monographs","author":"G Everest","year":"2003","unstructured":"Everest, G., van der Poorten, A.J., Shparlinski, I.E., Ward, T.: Recurrence Sequences, Mathematical surveys and monographs, vol. 104. American Mathematical Society, Providence (2003)"},{"issue":"4","key":"25_CR12","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/3157831.3157833","volume":"4","author":"N Fijalkow","year":"2017","unstructured":"Fijalkow, N.: Undecidability results for probabilistic automata. ACM SIGLOG News 4(4), 10\u201317 (2017). \n                      https:\/\/doi.org\/10.1145\/3157831.3157833","journal-title":"ACM SIGLOG News"},{"key":"25_CR13","doi-asserted-by":"publisher","unstructured":"Fijalkow, N., Klin, B., Panangaden, P.: Expressiveness of probabilistic modal logics, revisited. In: Chatzigiannakis, Y., Indyk, P., Kuhn, F., Muscholl, A. (eds.) Proc. of 44th Int. Coll. on Automata, Languages and Programming, ICALP 2017, Warsaw, July 2017. Leibniz International Proceedings in Informatics, vol. 80, Article no. 105. Dagstuhl Publishing, Saarbr\u00fccken\/Wadern (2017). \n                      https:\/\/doi.org\/10.4230\/lipics.icalp.2017.105","DOI":"10.4230\/lipics.icalp.2017.105"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-662-44602-7_21","volume-title":"Theoretical Computer Science","author":"S Goncharov","year":"2014","unstructured":"Goncharov, S., Milius, S., Silva, A.: Towards a coalgebraic Chomsky hierarchy (extended abstract). In: D\u00edaz, J., Lanese, I., Sangiorgi, D. (eds.) TCS 2014. LNCS, vol. 8705, pp. 265\u2013280. Springer, Heidelberg (2014). \n                      https:\/\/doi.org\/10.1007\/978-3-662-44602-7_21"},{"issue":"4","key":"25_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00450-013-0251-7","volume":"28","author":"TA Henzinger","year":"2013","unstructured":"Henzinger, T.A.: Quantitative reactive modeling and verification. Comput. Sci. Res. Dev. 28(4), 331\u2013344 (2013). \n                      https:\/\/doi.org\/10.1007\/s00450-013-0251-7","journal-title":"Comput. Sci. Res. Dev."},{"key":"25_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-642-17071-3_16","volume-title":"Formal Methods for Components and Objects","author":"H Hermanns","year":"2010","unstructured":"Hermanns, H., Katoen, J.: The how and why of interactive Markov chains. In: de Boer, F.S., Bonsangue, M.M., Hallerstede, S., Leuschel, M. (eds.) FMCO 2009. LNCS, vol. 6286, pp. 311\u2013337. Springer, Heidelberg (2010). \n                      https:\/\/doi.org\/10.1007\/978-3-642-17071-3_16"},{"key":"25_CR17","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 - Concurrency Theory","author":"H Hermanns","year":"2014","unstructured":"Hermanns, H., Krc\u00e1l, J., Kret\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). \n                      https:\/\/doi.org\/10.1007\/978-3-662-44584-6_18"},{"key":"25_CR18","doi-asserted-by":"publisher","unstructured":"Kozen, D.: Semantics of probabilistic programs. In: Proceedings of 20th Annual Symposium on Foundations of Computer Science, FOCS 1979, San Juan, PR, October 1979, pp. 101\u2013114. IEEE CS Press, Washington, D.C. (1979). \n                      https:\/\/doi.org\/10.1109\/sfcs.1979.38","DOI":"10.1109\/sfcs.1979.38"},{"key":"25_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-642-22110-1_47","volume-title":"Computer Aided Verification","author":"M Kwiatkowska","year":"2011","unstructured":"Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 585\u2013591. Springer, Heidelberg (2011). \n                      https:\/\/doi.org\/10.1007\/978-3-642-22110-1_47"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-540-78800-3_13","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A Legay","year":"2008","unstructured":"Legay, A., Murawski, A.S., Ouaknine, J., Worrell, J.: On automated verification of probabilistic programs. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 173\u2013187. Springer, Heidelberg (2008). \n                      https:\/\/doi.org\/10.1007\/978-3-540-78800-3_13"},{"key":"25_CR21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","year":"2014","unstructured":"Ouaknine, J., Worrell, J.: Positivity problems for low-order linear recurrence sequences. In: Proceedings of 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, January 2014, pp. 366\u2013379. SIAM (2014). \n                      https:\/\/doi.org\/10.1137\/1.9781611973402"},{"key":"25_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/c2013-0-11297-4","volume-title":"Introduction to Probabilistic Automata","author":"A Paz","year":"1971","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York\/London (1971). \n                      https:\/\/doi.org\/10.1016\/c2013-0-11297-4"},{"issue":"3","key":"25_CR23","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(3), 230\u2013245 (1963). \n                      https:\/\/doi.org\/10.1016\/s0019-9958(63)90290-0","journal-title":"Inf. Control"},{"key":"25_CR24","first-page":"21","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"MO Rabin","year":"1976","unstructured":"Rabin, M.O.: Probabilistic algorithms. In: Traub, J.F. (ed.) Algorithms and Complexity: New Directions and Recent Results, pp. 21\u201339. Academic Press, New York (1976)"},{"issue":"1","key":"25_CR25","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0022-0000(82)90010-1","volume":"25","author":"MO Rabin","year":"1982","unstructured":"Rabin, M.O.: \n                      \n                        \n                      \n                      $$N$$\n                      \n                        \n                          N\n                        \n                      \n                    -process mutual exclusion with bounded waiting by \n                      \n                        \n                      \n                      $$4 \\log _2 N$$\n                      \n                        \n                          \n                            4\n                            \n                              log\n                              2\n                            \n                            N\n                          \n                        \n                      \n                    -valued shared variable. J. Comput. Syst. Sci. 25(1), 66\u201375 (1982). \n                      https:\/\/doi.org\/10.1016\/0022-0000(82)90010-1","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"25_CR26","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1023\/a:1026490906255","volume":"25","author":"D Ron","year":"1996","unstructured":"Ron, D., Singer, Y., Tishby, N.: The power of amnesia: learning probabilistic automata with variable memory length. Mach. Learn. 25(2), 117\u2013149 (1996). \n                      https:\/\/doi.org\/10.1023\/a:1026490906255","journal-title":"Mach. Learn."},{"issue":"1\u20132","key":"25_CR27","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/s0304-3975(96)80710-9","volume":"170","author":"V Sassone","year":"1996","unstructured":"Sassone, V., Nielsen, M., Winskel, G.: Models for concurrency: towards a classification. Theor. Comput. Sci. 170(1\u20132), 297\u2013348 (1996). \n                      https:\/\/doi.org\/10.1016\/s0304-3975(96)80710-9","journal-title":"Theor. Comput. Sci."},{"key":"25_CR28","unstructured":"Segala, R.: Modeling and verification of randomized distributed real-time systems. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge (1995)"},{"key":"25_CR29","doi-asserted-by":"publisher","unstructured":"Silva, A., Bonchi, F., Bonsangue, M.M., Rutten, J.J.M.M.: Generalizing determinization from automata to coalgebras. Log. Methods Comput. Sci. 9(1), Article no. 9 (2013). \n                      https:\/\/doi.org\/10.2168\/lmcs-9(1:9)2013","DOI":"10.2168\/lmcs-9(1:9)2013"},{"issue":"4","key":"25_CR30","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s00165-012-0231-x","volume":"24","author":"M Swaminathan","year":"2012","unstructured":"Swaminathan, M., Katoen, J.P., Olderog, E.R.: Layered reasoning for randomized distributed algorithms. Form. Asp. Comput. 24(4), 477\u2013496 (2012). \n                      https:\/\/doi.org\/10.1007\/s00165-012-0231-x","journal-title":"Form. Asp. Comput."},{"key":"25_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45319-9_1","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"MY Vardi","year":"2001","unstructured":"Vardi, M.Y.: Branching vs. linear time: final showdown. In: Margaria, T., Yi, W. (eds.) TACAS 2001. LNCS, vol. 2031, pp. 1\u201322. Springer, Heidelberg (2001)"},{"key":"25_CR32","unstructured":"Vignudelli, V.: Behavioral equivalences for higher-order languages with probabilities. Ph.D. thesis, Univ. di Bologna (2017)"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2018"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-02508-3_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,3]],"date-time":"2020-03-03T02:49:00Z","timestamp":1583203740000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-02508-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030025076","9783030025083"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-02508-3_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"15 October 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICTAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Theoretical Aspects of Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Stellenbosch","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"South Africa","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 October 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 October 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ictac2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.ictac.org.za\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}