Title :
A deterministic parallel algorithm for the homing sequence problem
Author_Institution :
D Dept. of Computer Sci., Rhode Island Univ., Kingston, RI, USA
Abstract :
Homing sequences play an important role in the testing of finite state systems and have been used in a number of applications such as hardware fault detection, protocol verification, and learning algorithms etc. Recent applications of homing sequences involve large DFAs with thousands of states. Such applications motivate the design of a parallel algorithm for this problem. The author present a deterministic parallel algorithm of time complexity O(√nlog2n) using a polynomial number of processors on the CREW PRAM model. No faster deterministic parallel algorithm is known for this problem. The author also discusses the parallel complexity of some related problems
Keywords :
computational complexity; deterministic algorithms; deterministic automata; finite automata; parallel algorithms; sequences; CREW PRAM model; deterministic parallel algorithm; finite state system testing; hardware fault detection; homing sequence problem; learning algorithms; parallel algorithm design; parallel complexity; protocol verification; time complexity; Algorithm design and analysis; Application software; Automata; Computer science; Doped fiber amplifiers; Fault detection; Hardware; Parallel algorithms; Polynomials; Protocols;
Conference_Titel :
Parallel and Distributed Processing, 1996., Eighth IEEE Symposium on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-8186-7683-3
DOI :
10.1109/SPDP.1996.570376
