Authors: Colcombet Thomas, Fijalkow Nathanaël, Ohlmann Pierre Published on:-Publication:
Foundations of Software Science and Computation Structures;12077:119-35 DOI: 10.1007/978-3-030-45231-5_7
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.
Article Analysis: --
No tags are applied.
No tags found.
Additional Information
Journal:
Journal Article
Source:
PMC: PMC7788608
issn_isbn:
-
Country:
-
Language:
eng
article_id: 563825
More Info | #563825: Controlling a Random Population.
View PDF / Links: (#563825Controlling a Random Population.)