Randomized parallel algorithms for the homing sequence problem

Homing sequences play an important role in the testing of finite state systems and have been recently used in learning algorithms due to Rivest and Schapire (1993) and Freund et al. (1993). It is well-known that every minimal DFA has a homing sequence of length O(n²) which can be constructed sequentially in time O(n³). But no efficient parallel algorithm was known for this problem. We present two RNC algorithms of time complexity O(log²n) for this problem. We show that one of our RNC algorithms produces a homing sequence of length O(n logan) for almost all DFA´s with n states using a random model of Traktenbrot and Barzdin (1973). We also discuss connections between the homing sequence problem and other problems in the field of hardware fault-testing and protocol verification