On the complexity of existence of homing sequences for nondeterministic finite state machines
Natalia Kushik, V. V. Kulyamin, Н. В. Евтушенко · Programming and Computer Software · 2014
The paper discusses complexity of the problem of checking existence of a homing sequence for an observable complete finite state machines (FSMs). The minimum length of such a sequence for FSMs of certain class is known to be exponential in the number of the FSM states. It is shown that the problem of checking the existence of such a sequence belongs to class PSPACE.