文章基本信息

标题：CONTROLLING A RANDOM POPULATION
本地全文：下载
作者：Thomas Colcombet ; Nathanaël Fijalkow ; Pierre Ohlmann 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2021
卷号：17
期号：4
页码：1-21
DOI：10.46298/lmcs-17(4:12)2021
语种：English
出版社：Technical University of Braunschweig
摘要：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.
关键词：Parameterized Verification;Population Protocols;Parameterized Synthesis;Markov Decision Processes;Regular Cost Functions;Games