A Note on Undecidability of Observation Consistency for Non-Regular Languages

One of the most interesting questions concerning hierarchical control of discrete-event systems with partial observations is a condition under which the language observability is preserved between the original and the abstracted plant. Recently, we have characterized two such sufficient conditions—observation consistency and local observation consistency. In this paper, we prove that the condition of observation consistency is undecidable for non-regular (linear, deterministic context-free) languages. The question whether the condition is decidable for regular languages is open.