Abstract
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 EXPTIME-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.
The authors are committed to making professional choices acknowledging the climate emergency. We submitted this work to FoSSaCS for its excellence and because its location induces for us a low carbon footprint. This work was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 670624), and by the DeLTA ANR project (ANR-16-CE40-0007).
Chapter PDF
Similar content being viewed by others
References
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
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–253 (2006). https://doi.org/10.1007/s00446-005-0138-3
Bertrand, N., Dewaskar, M., Genest, B., Gimbert, H.: Controlling a population. In: CONCUR. pp. 12:1–12:16 (2017). https://doi.org/10.4230/LIPIcs.CONCUR.2017.12
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
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
Dickson, L.E.: Finiteness of the odd perfect and primitive abundant numbers with \(n\) distinct prime factors. American Journal of Mathematics 35(4), 413–422 (1913), http://www.jstor.org/stable/2370405
Esparza, J.: Parameterized verification of crowds of anonymous processes. In: Dependable Software Systems Engineering, pp. 59–71. IOS Press (2016). https://doi.org/10.3233/978-1-61499-627-9-59
Esparza, J., Finkel, A., Mayr, R.: On the verification of broadcast protocols. In: LICS. pp. 352–359 (1999). https://doi.org/10.1109/LICS.1999.782630
Fijalkow, N.: Undecidability results for probabilistic automata. SIGLOG News 4(4), 10–17 (2017), https://dl.acm.org/citation.cfm?id=3157833
Fijalkow, N., Gimbert, H., Horn, F., Oualhadj, Y.: Two recursively inseparable problems for probabilistic automata. In: MFCS. pp. 267–278 (2014). https://doi.org/10.1007/978-3-662-44522-8_23
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian Journal of Mathematics 8, 399–404 (1956). https://doi.org/10.4153/CJM-1956-045-5
German, S.M., Sistla, A.P.: Reasoning about systems with many processes. Journal of the ACM 39(3), 675–735 (1992)
Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: Decidable and undecidable problems. In: ICALP. pp. 527–538 (2010). https://doi.org/10.1007/978-3-642-14162-1_44
Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games, LNCS, vol. 2500. Springer (2002)
Higman, G.: Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society s3-2(1), 326–336 (1952). https://doi.org/10.1112/plms/s3-2.1.326
Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. J. Comb. Theory, Ser. A 13(3), 297–305 (1972). https://doi.org/10.1016/0097-3165(72)90063-5
Kuc̆era, A.: Turn-Based Stochastic Games. Lectures in Game Theory for Computer Scientists, Cambridge University Press (2011)
Mascle, C., Shirmohammadi, M., Totzke, P.: Controlling a random population is EXPTIME-hard. CoRR (2019), http://arxiv.org/abs/1909.06420
Schmitz, S.: Algorithmic Complexity of Well-Quasi-Orders. Habilitation à diriger des recherches, École normale supérieure Paris-Saclay (Nov 2017), https://tel.archives-ouvertes.fr/tel-01663266
Thomas, W.: Languages, automata, and logic. In: Handbook of Formal Language Theory, vol. III, pp. 389–455. Springer (1997)
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–285 (2015)
Valk, R., Jantzen, M.: The residue of vector sets with applications to decidability problems in Petri nets. Acta Informatica 21, 643–674 (03 1985). https://doi.org/10.1007/BF00289715
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Colcombet, T., Fijalkow, N., Ohlmann, P. (2020). Controlling a Random Population. In: Goubault-Larrecq, J., König, B. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2020. Lecture Notes in Computer Science(), vol 12077. Springer, Cham. https://doi.org/10.1007/978-3-030-45231-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-45231-5_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45230-8
Online ISBN: 978-3-030-45231-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)