LARSEN, Kim G., Simon LAURSEN and Jiří SRBA. Synchronizing Strategies under Partial Observability. In Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'14). Nizozemsko: Springer-Verlag. p. 188-202. ISBN 978-3-662-44583-9. doi:10.1007/978-3-662-44584-6_14. 2014.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Synchronizing Strategies under Partial Observability
Authors LARSEN, Kim G. (208 Denmark), Simon LAURSEN (208 Denmark) and Jiří SRBA (203 Czech Republic, guarantor, belonging to the institution).
Edition Nizozemsko, Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'14), p. 188-202, 15 pp. 2014.
Publisher Springer-Verlag
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
WWW Link
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/14:00080034
Organization unit Faculty of Informatics
ISBN 978-3-662-44583-9
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-662-44584-6_14
Keywords in English synchronization problem; finite automata; partial observability; complexity
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: Prof. Jiří Srba, Ph.D., učo 2841. Changed: 10/4/2015 08:39.
Abstract
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.
PrintDisplayed: 23/4/2024 10:07