Synchronizing Strategies under Partial Observability

D 2014

Synchronizing Strategies under Partial Observability

LARSEN, Kim G., Simon LAURSEN a Jiří SRBA

Základní údaje

Originální název

Synchronizing Strategies under Partial Observability

Autoři

LARSEN, Kim G. (208 Dánsko), Simon LAURSEN (208 Dánsko) a Jiří SRBA (203 Česká republika, garant, domácí)

Vydání

Nizozemsko, Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'14), od s. 188-202, 15 s. 2014

Nakladatel

Springer-Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

Link

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/14:00080034

Organizační jednotka

Fakulta informatiky

ISBN

978-3-662-44583-9

ISSN

DOI

http://dx.doi.org/10.1007/978-3-662-44584-6_14

Klíčová slova anglicky

synchronization problem; finite automata; partial observability; complexity

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 10. 4. 2015 08:39, Prof. Jiří Srba, Ph.D.

Anotace

V originále

Embedded devices usually share only partial information about their current configurations as the communication bandwidth can be restricted. Despite this, we may wish to bring a failed device into a given predetermined configuration. This problem, also known as resetting or synchronizing words, has been intensively studied for systems that do not provide any information about their configurations. In order to capture more general scenarios, we extend the existing theory of synchronizing words to synchronizing strategies, and study the synchronization, short-synchronization and subset-to-subset synchronization problems under partial observability. We provide a comprehensive complexity analysis of these problems, concluding that for deterministic systems the complexity of the problems under partial observability remains the same as for the classical synchronization problems, whereas for nondeterministic systems the complexity increases already for systems with just two observations, as we can now encode alternation.

Citovat

LARSEN, Kim G., Simon LAURSEN a Jiří SRBA. Synchronizing Strategies under Partial Observability. In Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'14). Nizozemsko: Springer-Verlag, 2014, s. 188-202. ISBN 978-3-662-44583-9. Dostupné z: https://dx.doi.org/10.1007/978-3-662-44584-6_14.

@inproceedings{1297400,
   author = {Larsen, Kim G. and Laursen, Simon and Srba, Jiří},
   address = {Nizozemsko},
   booktitle = {Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'14)},
   doi = {http://dx.doi.org/10.1007/978-3-662-44584-6_14},
   keywords = {synchronization problem; finite automata; partial observability; complexity},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Nizozemsko},
   isbn = {978-3-662-44583-9},
   pages = {188-202},
   publisher = {Springer-Verlag},
   title = {Synchronizing Strategies under Partial Observability},
   url = {http://link.springer.com/chapter/10.1007/978-3-662-44584-6_14},
   year = {2014}
}

TY  - JOUR
ID  - 1297400
AU  - Larsen, Kim G. - Laursen, Simon - Srba, Jiří
PY  - 2014
TI  - Synchronizing Strategies under Partial Observability
PB  - Springer-Verlag
CY  - Nizozemsko
SN  - 9783662445839
KW  - synchronization problem
KW  - finite automata
KW  - partial observability
KW  - complexity
UR  - http://link.springer.com/chapter/10.1007/978-3-662-44584-6_14
L2  - http://link.springer.com/chapter/10.1007/978-3-662-44584-6_14
N2  - Embedded devices usually share only partial information about their current configurations as the communication bandwidth can be restricted. Despite this, we may wish to bring a failed device into a given predetermined configuration. This problem, also known as resetting or synchronizing words, has been intensively studied for systems that do not provide any information about their configurations. In order to capture more general scenarios, we extend the existing theory of synchronizing words to synchronizing strategies, and study the synchronization, short-synchronization and subset-to-subset synchronization problems under partial observability. We provide a comprehensive complexity analysis of these problems, concluding that for deterministic systems the complexity of the problems under partial observability remains the same as for the classical synchronization problems, whereas for nondeterministic systems the complexity increases already for systems with just two observations, as we can now encode alternation.
ER  -

LARSEN, Kim G., Simon LAURSEN a Jiří SRBA. Synchronizing Strategies under Partial Observability. In \textit{Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'14)}. Nizozemsko: Springer-Verlag, 2014, s.~188-202. ISBN~978-3-662-44583-9. Dostupné z: https://dx.doi.org/10.1007/978-3-662-44584-6\_{}14.

Podrobný výpis o publikaci