Distributed synthesis in continuous time.

HERMANNS, Holger, Jan KRČÁL and Steen VESTER. Distributed synthesis in continuous time. In International Conference on Foundations of Software Science and Computation Structures. Berlin: Springer. p. 353-369. ISBN 978-3-662-49629-9. doi:10.1007/978-3-662-49630-5_21. 2016.

Basic information

• Original name: Distributed synthesis in continuous time.
• Authors: HERMANNS, Holger (276 Germany), Jan KRČÁL (203 Czech Republic, guarantor, belonging to the institution) and Steen VESTER (208 Denmark).
• Edition: Berlin, International Conference on Foundations of Software Science and Computation Structures. p. 353-369, 17 pp. 2016.
• Publisher: Springer

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• Impact factor: Impact factor: 0.402 in 2005
• RIV identification code: RIV/00216224:14330/16:00088813
• Organization unit: Faculty of Informatics
• ISBN: 978-3-662-49629-9
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-662-49630-5_21
• Keywords in English: distributed controller synthesis; interactive Markov chains; undecidabiliy
• Tags: core_A, firank_A

Abstract

We introduce a formalism modelling communication of distributed agents strictly in continuous-time. Within this framework, we study the problem of synthesising local strategies for individual agents such that a specified set of goal states is reached, or reached with at least a given probability. The flow of time is modelled explicitly based on continuous-time randomness, with two natural implications: First, the non-determinism stemming from interleaving disappears. Second, when we restrict to a subclass of non-urgent models, the quantitative value problem for two players can be solved in EXPTIME. Indeed, the explicit continuous time enables players to communicate their states by delaying synchronisation (which is unrestricted for non-urgent models). In general, the problems are undecidable already for two players in the quantitative case and three players in the qualitative case. The qualitative undecidability is shown by a reduction to decentralized POMDPs for which we provide the strongest (and rather surprising) undecidability result so far.

Links

• GBP202/12/G061, research and development project: Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)

Investor: Czech Science Foundation