Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10413062 | Systems & Control Letters | 2005 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Engineering
Control and Systems Engineering
Authors
J.G. Thistle,