Thomas Colcombet ; Nathanaël Fijalkow ; Pierre Ohlmann - Controlling a random population

lmcs:7034 - Logical Methods in Computer Science, November 24, 2021, Volume 17, Issue 4 - https://doi.org/10.46298/lmcs-17(4:12)2021
Controlling a random populationArticle

Authors: Thomas Colcombet ORCID; 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.


    Volume: Volume 17, Issue 4
    Published on: November 24, 2021
    Accepted on: September 28, 2021
    Submitted on: January 1, 2021
    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
    Funding:
      Source : OpenAIRE Graph
    • 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

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1237 times.
    This article's PDF has been downloaded 270 times.