On minimizing the lengths of checking sequences

被引：82
作者：
Ural, H
Wu, XL
Zhang, F
机构：
[1] BELL NO RES LTD, OTTAWA, ON K1Y 4H7, CANADA
[2] CITY UNIV HONG KONG, DEPT COMP SCI, KOWLOON, HONG KONG
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1997年 / 46卷 / 01期
基金：
加拿大自然科学与工程研究理事会;
关键词：
finite state machines; fault detection; checking experiments; checking sequences; testing;
D O I：
10.1109/12.559807
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A general model for constructing minimal length checking sequences employing a distinguishing sequence is proposed. The model is based on characteristics of checking sequences and a set of state recognition sequences. Some existing methods are shown to be special cases of the proposed model and are proven to construct checking sequences. The minimality of the resulting checking sequences is discussed and a heuristic algorithm for the construction of minimal length checking sequences is given.
引用
收藏
页码：93 / 99
页数：7
相关论文
共 15 条
[1]   AN OPTIMIZATION TECHNIQUE FOR PROTOCOL CONFORMANCE TEST-GENERATION BASED ON UIO SEQUENCES AND RURAL CHINESE POSTMAN TOURS [J].
AHO, AV ;
DAHBURA, AT ;
LEE, D ;
UYAR, MU .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1991, 39 (11) :1604-1615
[2]  
[Anonymous], CHINESE MATH
[3]  
BONDY JA, 1976, GRAPH THEORY APPLICA
[4]   ON THE COMPLEXITY OF GENERATING OPTIMAL TEST SEQUENCES [J].
BOYD, SC ;
URAL, H .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1991, 17 (09) :976-978
[5]   FORMAL METHODS FOR GENERATING PROTOCOL CONFORMANCE TEST SEQUENCES [J].
DAHBURA, AT ;
SABNANI, KK ;
UYAR, MU .
PROCEEDINGS OF THE IEEE, 1990, 78 (08) :1317-1326
[6]  
Edmonds J., 1973, Mathematical Programming, V5, P88, DOI 10.1007/BF01580113
[7]  
Gill A., 1962, INTRO THEORY FINITE
[8]   A METHOD FOR DESIGN OF FAULT DETECTION EXPERIMENTS [J].
GONENC, G .
IEEE TRANSACTIONS ON COMPUTERS, 1970, C 19 (06) :551-+
[9]  
HENNIE FC, 1964, 5TH P ANN S SWITCH C, P95
[10]  
Lawler EL., 2001, Combinatorial optimization: networks and matroids
12