Synchronizing Strategies under Partial Observability

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

9 Citationer (Scopus)
317 Downloads (Pure)

Abstrakt

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.
OriginalsprogEngelsk
TitelCONCUR 2014 – Concurrency Theory
RedaktørerPaolo Baldan, Daniele Gorla
Vol/bind8704
ForlagSpringer Publishing Company
Publikationsdato2014
Sider188-202
ISBN (Trykt)9783662445839, 03029743
ISBN (Elektronisk)9783662445846, 16113349
DOI
StatusUdgivet - 2014
BegivenhedCONCUR 2014: Concurrency Theory - University of Rome - La Sapienza, Rome, Italien
Varighed: 2 sep. 20145 sep. 2014
Konferencens nummer: 25

Konference

KonferenceCONCUR 2014
Nummer25
LokationUniversity of Rome - La Sapienza
LandItalien
ByRome
Periode02/09/201405/09/2014
NavnLecture Notes in Computer Science
ISSN0302-9743

Fingeraftryk Dyk ned i forskningsemnerne om 'Synchronizing Strategies under Partial Observability'. Sammen danner de et unikt fingeraftryk.

Citationsformater