Distributed synthesis in continuous time.

D 2016

Distributed synthesis in continuous time.

HERMANNS, Holger; Jan KRČÁL a Steen VESTER

Základní údaje

Originální název

Distributed synthesis in continuous time.

Autoři

HERMANNS, Holger; Jan KRČÁL a Steen VESTER

Vydání

Berlin, International Conference on Foundations of Software Science and Computation Structures. od s. 353-369, 17 s. 2016

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/16:00088813

Organizační jednotka

Fakulta informatiky

ISBN

978-3-662-49629-9

ISSN

Klíčová slova anglicky

distributed controller synthesis; interactive Markov chains; undecidabiliy

Štítky

core_A, firank_A

Změněno: 25. 10. 2024 16:29, Mgr. Natálie Hílek

Anotace

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.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

Citovat

HERMANNS, Holger; Jan KRČÁL a Steen VESTER. Distributed synthesis in continuous time. In International Conference on Foundations of Software Science and Computation Structures. Berlin: Springer, 2016, s. 353-369. ISBN 978-3-662-49629-9. Dostupné z: https://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 = {https://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  - CONF
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 a Steen VESTER. Distributed synthesis in continuous time. In \textit{International Conference on Foundations of Software Science and Computation Structures.}. Berlin: Springer, 2016, s.~353-369. ISBN~978-3-662-49629-9. Dostupné z: https://doi.org/10.1007/978-3-662-49630-5\_{}21.

Přehled o publikaci