2022/04/22 by Ritsuka, K., Karen Rudie, Rudie, Karen
Computer Science · Engineering · #Advanced Memory and Neural Computing #Distributed systems and fault tolerance #FOS: Electrical engineering #Petri Nets in System Modeling #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2204.10792
openalex publication_date 2022/04/22 · openalex created_date 2022/04/27 · openalex updated_date 2026/07/28
This paper demonstrates an equivalence between observation problems, control problems (with partial observation), and diagnosis problems of decentralized discrete-event systems, namely, the three classes of problems are Turing equivalent, as one class Turing reduces to another. The equivalence allows decomposition of a control problem into a collection of simpler control sub\-/problems, which are each equivalent to an observation problem; and similarly allows converting a diagnosis problem to a formally simpler observation problem. Since observation problems in their most general formulation have been shown to be undecidable in previous work, the equivalence produced here demonstrates that control problems are also undecidable; whereas the undecidability of diagnosis problems is a known result.