loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fifth International Conference on Application of Concurrency to System Design (ACSD'05)
Two-Phase Distributed Observation Problems
St. Malo, France
June 07-June 09
ISBN: 0-7695-2363-3
Stavros Tripakis, Verimag Laboratory
We introduce and study problems of distributed observation with bounded or unbounded memory. We are given a system modeled as a finite-word language L over some fi- nite alphabet ? and subalphabets \sum _{1, \ldots ,} \sum _n of ? modeling n distinct observation points. We want to build (when there exist) n observers which collect projections of a behavior in L onto \sum _{1, \ldots ,} \sum _n then send them to a central decision point. The latter must determine whether the original behavior was in a given K ? L. In the unbounded-memory case, observers record the entire sequence they observe. In the bounded-memory case, they are required to be finitestate automata. We show that, when L is trace-closed with respect to the usual dependence relation induced by \sum _{1, \ldots ,} \sum _n unbounded-memory observability is equivalent to K being centrally observable and trace-closed, thus decidable. When L is not trace-closed, the problem is undecidable, even if K and L are regular. We also show that boundedmemory observability is equivalent to unbounded-memory observability (thus decidable) when L is trace-closed and \sum {_i } are pairwise disjoint. Otherwise, the problem remains open. In the decidable cases, observers and decision function can be automatically synthesized.
Citation:
Stavros Tripakis, "Two-Phase Distributed Observation Problems," acsd, pp.98-105, Fifth International Conference on Application of Concurrency to System Design (ACSD'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.