| Randomized Parallel Algorithms For The Homing Sequence Problem (1996) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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 [17] and Freund et al. [4]. It is well-known that every minimal DFA has a homing sequence of length O(n 2 ) which can be constructed sequentially in time O(n 3 ). But no efficient parallel algorithm was known for this problem. In this work, we present two RNC algorithms of time complexity O(log 2 n) for this problem. We show that one of our RNC algorithms produces a homing sequence of length O(n log 2 n) for almost all DFA's with n states using a random model of Traktenbrot and Barzdin. We also discuss connections between the homing sequence problem and other problems in the field of hardware fault-testing and protocol verification. 1. INTRODUCTION Locating the current state in a finite-state system is a fundamental problem in map-learning and robotics. This problem has many variations. The version we consider in this pape... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||