Undecidable problems of decentralized observation and control on regular languages

We introduce a decentralized observation problem, where the system under observation is modeled as a regular language L over a finite alphabet Sigma and n subsets of Sigma model distributed observation points. A regular language K subset of or equal to L models a set of distinguished behaviors, say, correct behaviors of the system. The objective is to check the existence of a function which, given the n observations corresponding to a behavior rho is an element of L, decides whether rho is in K or not. We prove that checking the existence of such a function is undecidable. We then use this result to show undecidability of a decentralized supervisory control problem in the discrete event system framework. (C) 2004 Elsevier B.V. All rights reserved.