Undecidability in decentralized supervision

It is well known that supervisor synthesis problems involving partial observations generally have high computational complexity, but was only recently shown (in the preliminary version of this article) that the solvability of decentralized supervisor synthesis problems may be undecidable, even in cases where all pertinent languages are represented as finite automata. The result is established by reduction from the halting problem for Turing machines. Alternative proofs, discovered independently by other authors, employ a reduction from Post's correspondence problem. (c) 2004 Elsevier B.V. All rights reserved.