Decentralized control of discrete event systems with bounded or unbounded delay communication

We introduce problems of decentralized control with delayed communication, where delays are either unbounded or bounded by a given constant k. In the k-bounded-delay model, between the transmission of a message and its reception, the plant can execute at most k events. In the unbounded-delay model, the plant can execute any number of events between transmission and reception. We show that our framework yields an infinite hierarchy of control problems, 𝒞𝒞 =𝒟𝒞𝒞₀⊃𝒟𝒞𝒞₁⊃𝒟𝒞𝒞₂⊃···⊃𝒟𝒞𝒰𝒞⊃𝒟𝒞 , where CC is the set of control problems solvable with a single controller (centralized case) and 𝒟𝒞𝒞_k (resp. 𝒟𝒞𝒰𝒞, 𝒟𝒞) is the set of problems solvable with two controllers in a k-bounded-delay network (resp. two controllers in an unbounded-delay network, two controllers without communication). The above containments are strict. We prove the undecidability of checking the existence of controllers in the unbounded-delay case, or in the case without any communication. Finally, we prove that a decentralized observation problem with bounded-delay communication is decidable.