Detailed Information on Publication Record
2014
Synchronizing Strategies under Partial Observability
LARSEN, Kim G., Simon LAURSEN and Jiří SRBABasic 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
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
References:
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
Keywords in English
synchronization problem; finite automata; partial observability; complexity
Tags
International impact, Reviewed
Změněno: 10/4/2015 08:39, Prof. Jiří Srba, Ph.D.
Abstract
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.