Two-phase distributed observation problems

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 finite alphabet Sigma and subalphabets Sigma(n) of Sigma modeling n distinct observation points. We want to build (when there exist) n observers which collect projections of a behavior in L onto Sigma(1), ... , E-n, then send them to a central decision point. The latter must determine whether the original behavior was in a given K subset of L. In the unbounded-memory case, observers record the entire sequence they observe. In the bounded-memory case, they are required to be finite-state automata. We show that, when L is trace-closed with respect to the usual dependence relation induced by Sigma(1) ,..., Sigma(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 bounded-memory observability is equivalent to unbounded-memory observability (thus decidable) when L is trace-closed and Sigma(i) are pairwise disjoint Otherwise, the problem remains open. In the decidable cases, observers and decision function can be automatically synthesized.