Ural, Hasan,Wang, Zhiping.2009-03-232009-03-2319921992Source: Masters Abstracts International, Volume: 32-05, page: 1419.9780315857964http://hdl.handle.net/10393/7589http://dx.doi.org/10.20381/ruor-15413This study addresses the synchronization problem that arises during the application of a predetermined test sequence in some test architectures used for protocol conformance testing. A solution to this problem is to construct synchronizable test sequences. For FSM-based protocol specifications, a necessary and sufficient condition is given for the existence of a synchronizable test sequence for a given FSM. A polynomial time algorithm is then developed to determine the existence of such a sequence for a given FSM. A duplex digraph method is developed which transforms the order-specified digraph representing an FSM into a duplex digraph. Using the duplex digraph representation of a given FSM, a polynomial time algorithm is developed to generate a synchronizable test sequence for the FSM which checks only the output function of the FSM. The W-, D- and UIO-methods are extended to an FSM represented by an order-specified digraph by employing synchronizable W-sets, synchronizable DS sequences and synchronizable UIO sequences, respectively. Polynomial time algorithms are then developed to generate synchronizable test sequences for a given FSM which check the transfer function as well as the output function.106 p.Computer Science.Thesis