Distributed synthesis in continuous time.

D 2016

Distributed synthesis in continuous time.

HERMANNS, Holger, Jan KRČÁL and Steen VESTER

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

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

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

DOI

http://dx.doi.org/10.1007/978-3-662-49630-5_21

UT WoS

000401936500021

Keywords in English

distributed controller synthesis; interactive Markov chains; undecidabiliy

Abstract

V originále

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

Citovat

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, 2016, p. 353-369. ISBN 978-3-662-49629-9. Available from: https://dx.doi.org/10.1007/978-3-662-49630-5_21.

@inproceedings{1377784,
   author = {Hermanns, Holger and Krčál, Jan and Vester, Steen},
   address = {Berlin},
   booktitle = {International Conference on Foundations of Software Science and Computation Structures.},
   doi = {http://dx.doi.org/10.1007/978-3-662-49630-5_21},
   keywords = {distributed controller synthesis; interactive Markov chains; undecidabiliy},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin},
   isbn = {978-3-662-49629-9},
   pages = {353-369},
   publisher = {Springer},
   title = {Distributed synthesis in continuous time.},
   year = {2016}
}

TY  - JOUR
ID  - 1377784
AU  - Hermanns, Holger - Krčál, Jan - Vester, Steen
PY  - 2016
TI  - Distributed synthesis in continuous time.
PB  - Springer
CY  - Berlin
SN  - 9783662496299
KW  - distributed controller synthesis
KW  - interactive Markov chains
KW  - undecidabiliy
N2  - 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.
ER  -

HERMANNS, Holger, Jan KRČÁL and Steen VESTER. Distributed synthesis in continuous time. In \textit{International Conference on Foundations of Software Science and Computation Structures.}. Berlin: Springer, 2016, p.~353-369. ISBN~978-3-662-49629-9. Available from: https://dx.doi.org/10.1007/978-3-662-49630-5\_{}21.

Detailed Information on Publication Record