Finding UIO Sequence is PSPACE-complete
A problem is said to be in PSPACE iff it can be solved by a Deterministic Turing Matching using only polynomial working space.
It is shown if [Lee], for a given machine M, the following three problem ate PSPACE-complete
Does a specific given states of M have a UIO sequence
Do all states of M have a UIO sequence.
Is there some state of M with a UIO sequence
Reference : David Lee and Mihalis Yannakakis, Testing Finite-State Machines: State Identification and Verification, IEEE Tran. on Computers, Vol, 43, No. 3, 1994