skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Controlling a random population

Logical methods in computer science, 2021-01, Vol.17, Issue 4 (4), p.119-135 [Peer Reviewed Journal]

Distributed under a Creative Commons Attribution 4.0 International License ;ISSN: 1860-5974 ;EISSN: 1860-5974 ;DOI: 10.46298/lmcs-17(4:12)2021

Full text available

Citations Cited by
  • Title:
    Controlling a random population
  • Author: Colcombet, Thomas ; Fijalkow, Nathanaël ; Ohlmann, Pierre
  • Subjects: Computer Science ; computer science - computer science and game theory ; computer science - distributed, parallel, and cluster computing ; computer science - formal languages and automata theory ; computer science - logic in computer science
  • Is Part Of: Logical methods in computer science, 2021-01, Vol.17, Issue 4 (4), p.119-135
  • Description: 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.
  • Publisher: Logical Methods in Computer Science Association
  • Language: English
  • Identifier: ISSN: 1860-5974
    EISSN: 1860-5974
    DOI: 10.46298/lmcs-17(4:12)2021
  • Source: Hyper Article en Ligne (HAL) (Open Access)
    Alma/SFX Local Collection
    ROAD: Directory of Open Access Scholarly Resources
    DOAJ Directory of Open Access Journals
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait