{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T01:19:14Z","timestamp":1790817554226,"version":"4.1.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030452308","type":"print"},{"value":"9783030452315","type":"electronic"}],"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>Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all agents to a target state? They showed that the problem is decidable and<jats:bold>EXPTIME<\/jats:bold>-complete in the adversarial setting, and posed as an open problem the stochastic setting, where the agent is represented by a Markov decision process. In this paper, we show that the stochastic control problem is decidable. Our solution makes significant uses of well quasi orders, of the max-flow min-cut theorem, and of the theory of regular cost functions.<\/jats:p>","DOI":"10.1007\/978-3-030-45231-5_7","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"119-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Controlling a Random Population"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Colcombet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathana\u00ebl","family":"Fijalkow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Ohlmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., Henda, N.B., Mayr, R.: Decisive Markov chains. Logical Methods in Computer Science 3(4) (2007). https:\/\/doi.org\/10.2168\/LMCS-3(4:7)2007","DOI":"10.2168\/LMCS-3(4:7)2007"},{"key":"7_CR2","doi-asserted-by":"publisher","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4), 235\u2013253 (2006). https:\/\/doi.org\/10.1007\/s00446-005-0138-3","DOI":"10.1007\/s00446-005-0138-3"},{"key":"7_CR3","doi-asserted-by":"publisher","unstructured":"Bertrand, N., Dewaskar, M., Genest, B., Gimbert, H.: Controlling a population. In: CONCUR. pp. 12:1\u201312:16 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2017.12","DOI":"10.4230\/LIPIcs.CONCUR.2017.12"},{"key":"7_CR4","unstructured":"Bertrand, N., Dewaskar, M., Genest, B., Gimbert, H., Godbole, A.A.: Controlling a population. Logical Methods in Computer Science 15(3) (2019), https:\/\/lmcs.episciences.org\/5647"},{"key":"7_CR5","doi-asserted-by":"publisher","unstructured":"Colcombet, T.: Regular cost functions, part I: logic and algebra over words. Logical Methods in Computer Science 9(3) (2013). https:\/\/doi.org\/10.2168\/LMCS-9(3:3)2013","DOI":"10.2168\/LMCS-9(3:3)2013"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Dickson, L.E.: Finiteness of the odd perfect and primitive abundant numbers with $$n$$ distinct prime factors. American Journal of Mathematics 35(4), 413\u2013422 (1913), http:\/\/www.jstor.org\/stable\/2370405","DOI":"10.2307\/2370405"},{"key":"7_CR7","doi-asserted-by":"publisher","unstructured":"Esparza, J.: Parameterized verification of crowds of anonymous processes. In: Dependable Software Systems Engineering, pp. 59\u201371. IOS Press (2016). https:\/\/doi.org\/10.3233\/978-1-61499-627-9-59","DOI":"10.3233\/978-1-61499-627-9-59"},{"key":"7_CR8","doi-asserted-by":"publisher","unstructured":"Esparza, J., Finkel, A., Mayr, R.: On the verification of broadcast protocols. In: LICS. pp. 352\u2013359 (1999). https:\/\/doi.org\/10.1109\/LICS.1999.782630","DOI":"10.1109\/LICS.1999.782630"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Fijalkow, N.: Undecidability results for probabilistic automata. SIGLOG News 4(4), 10\u201317 (2017), https:\/\/dl.acm.org\/citation.cfm?id=3157833","DOI":"10.1145\/3157831.3157833"},{"key":"7_CR10","doi-asserted-by":"publisher","unstructured":"Fijalkow, N., Gimbert, H., Horn, F., Oualhadj, Y.: Two recursively inseparable problems for probabilistic automata. In: MFCS. pp. 267\u2013278 (2014). https:\/\/doi.org\/10.1007\/978-3-662-44522-8_23","DOI":"10.1007\/978-3-662-44522-8_23"},{"key":"7_CR11","doi-asserted-by":"publisher","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian Journal of Mathematics 8, 399\u2013404 (1956). https:\/\/doi.org\/10.4153\/CJM-1956-045-5","DOI":"10.4153\/CJM-1956-045-5"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"German, S.M., Sistla, A.P.: Reasoning about systems with many processes. Journal of the ACM 39(3), 675\u2013735 (1992)","DOI":"10.1145\/146637.146681"},{"key":"7_CR13","doi-asserted-by":"publisher","unstructured":"Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: Decidable and undecidable problems. In: ICALP. pp. 527\u2013538 (2010). https:\/\/doi.org\/10.1007\/978-3-642-14162-1_44","DOI":"10.1007\/978-3-642-14162-1_44"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games, LNCS, vol.\u00a02500. Springer (2002)","DOI":"10.1007\/3-540-36387-4"},{"key":"7_CR15","doi-asserted-by":"publisher","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society s3-2(1), 326\u2013336 (1952). https:\/\/doi.org\/10.1112\/plms\/s3-2.1.326","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"7_CR16","doi-asserted-by":"publisher","unstructured":"Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. J. Comb. Theory, Ser. A 13(3), 297\u2013305 (1972). https:\/\/doi.org\/10.1016\/0097-3165(72)90063-5","DOI":"10.1016\/0097-3165(72)90063-5"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Kuc\u0306era, A.: Turn-Based Stochastic Games. Lectures in Game Theory for Computer Scientists, Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511973468.006"},{"key":"7_CR18","unstructured":"Mascle, C., Shirmohammadi, M., Totzke, P.: Controlling a random population is EXPTIME-hard. CoRR (2019), http:\/\/arxiv.org\/abs\/1909.06420"},{"key":"7_CR19","unstructured":"Schmitz, S.: Algorithmic Complexity of Well-Quasi-Orders. Habilitation \u00e0 diriger des recherches, \u00c9cole normale sup\u00e9rieure Paris-Saclay (Nov 2017), https:\/\/tel.archives-ouvertes.fr\/tel-01663266"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. In: Handbook of Formal Language Theory, vol.\u00a0III, pp. 389\u2013455. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Uhlendorf, J., Miermont, A., Delaveau, T., Charvin, G., Fages, F., Bottani, S., Hersen, P., Batt, G.: In silico control of biomolecular processes. Computational Methods in Synthetic Biology 13, 277\u2013285 (2015)","DOI":"10.1007\/978-1-4939-1878-2_13"},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"Valk, R., Jantzen, M.: The residue of vector sets with applications to decidability problems in Petri nets. Acta Informatica 21, 643\u2013674 (03 1985). https:\/\/doi.org\/10.1007\/BF00289715","DOI":"10.1007\/BF00289715"}],"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_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:46:34Z","timestamp":1666367194000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45231-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030452308","9783030452315"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45231-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"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)"}}]}}