New Algorithms for Verification of Relative Observability and Computation of Supremal Relatively Observable Sublanguage
Marcos V. S. Alves, Lilian K. Carvalho, João Carlos Basilio · IEEE Transactions on Automatic Control · 2016
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.