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. s. 188-202. ISBN 978-3-662-44583-9. doi:10.1007/978-3-662-44584-6_14. 2014.
Další formáty:   BibTeX LaTeX RIS
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
Originální 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"
WWW 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 0302-9743
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ěnil Změnil: Prof. Jiří Srba, Ph.D., učo 2841. Změněno: 10. 4. 2015 08:39.
Anotace
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.
VytisknoutZobrazeno: 29. 3. 2024 07:36