Authors: Thomas Colcombet ; Nathanaël Fijalkow ; Pierre Ohlmann
0000-0001-6529-6963##NULL##NULL
Thomas Colcombet;Nathanaël Fijalkow;Pierre Ohlmann
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. We
introduce an intermediate problem of independence interest called the
sequential flow problem and study its complexity.
Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Distributed, Parallel, and Cluster Computing,Computer Science - Computer Science and Game Theory,Computer Science - Logic in Computer Science
Duality in Formal Languages and Logic - a unifying approach to complexity and semantics; Funder: European Commission; Code: 670624
Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007
Bibliographic References
2 Documents citing this article
Laurent Doyen, 2023, Stochastic Games with Synchronization Objectives, Journal of the Association for Computing Machinery, 70, 3, pp. 1-35, 10.1145/3588866, https://doi.org/10.1145/3588866.