IEEE Transactions on Automatic Control, Vol.62, No.11, 5902-5908, 2017
New Algorithms for Verification of Relative Observability and Computation of Supremal Relatively Observable Sublanguage
In this technical note, we present a new property of relative observability, and based on this property, we propose two algorithms: the first one, that has polynomial complexity, verifies if a regular language is relatively observable; the second algorithm computes the supremal relatively observable sublanguage of a given regular language. Although the latter has exponential complexity, it is more efficient than a recently proposed algorithm, which has double exponential complexity. Moreover, the algorithm proposed here has polynomial complexity when the automaton that marks the specification language is state partition.