Optimal algorithm for constructing UIO sequence in finite-state machines

摘要：

The Finite state machine (FSM) is widely used to model hardware and software. Unique input/output sequence (UIO Sequence) is used to construct test sequences to verify whether the FSM is in a certain state. UIO sequence search process is to construct a UIO tree, but the partitioning node method will produce lots of unwanted nodes. With the existing method of constructing the UIO tree, the paper proposed an algorithm by classifying nodes as necessary and unnecessary nodes and recycling the chain-state technique to reduce the search space and speed up the process of UIO sequence generation. Comparing with previous algorithms, both of time complexity and space complexity have a greater improvement.

关键词： V10 sequence chain-state marked node

作者: Li Zhongwen Zhang Laishun

作者单位: Institute of Electronic Technology Information Engineering University Zhengzhou, China

会议类型: 国际会议

会议名称: 2010 International Conference on Software and Computing Technology(2010年软件与计算机技术国际会议 ICSCT 2010)

会议地点: 昆明

会议语种:英文

页码: 868-870

在线出版日期: 2010-10-17（万方平台首次上网日期，不代表论文的发表时间）