Principles and methods of testing finite state machines-a survey

有限状态机 计算机科学 一致性测试 国家(计算机科学) 任务(项目管理) 确定性有限自动机 自动机 扩展有限状态机 理论计算机科学 计算机工程 算法 系统工程 工程类 操作系统 标准化
作者
D. Lee,Mihalis Yannakakis
出处
期刊:Proceedings of the IEEE [Institute of Electrical and Electronics Engineers]
卷期号:84 (8): 1090-1123 被引量:1410
标识
DOI:10.1109/5.533956
摘要

With advanced computer technology, systems are getting larger to fulfill more complicated tasks: however, they are also becoming less reliable. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of testing finite stare machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of states and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse areas, including sequential circuits, certain types of programs, and, more recently, communication protocols. In a testing problem we have a machine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and observing the outputs produced. Because of its practical importance and theoretical interest, the problem of testing finite state machines has been studied in different areas and at various times. The earliest published literature on this topic dates back to the 1950's. Activities in the 1960's mid early 1970's were motivated mainly by automata theory and sequential circuit testing. The area seemed to have mostly died down until a few years ago when the testing problem was resurrected and is now being studied anew due to its applications to conformance testing of communication protocols. While some old problems which had been open for decades were resolved recently, new concepts and more intriguing problems from new applications emerge. We review the fundamental problems in testing finite state machines and techniques for solving these problems, tracing progress in the area from its inception to the present and the stare of the art. In addition, we discuss extensions of finite state machines and some other topics related to testing.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
刚刚
酷酷柚子发布了新的文献求助10
刚刚
刚刚
bkagyin的应助被Peetvader采纳,获得10
刚刚
1秒前
iris发布了新的文献求助10
1秒前
emmmmmmm001完成签到,获得积分10
1秒前
shadinganchun完成签到,获得积分10
2秒前
CipherSage的应助被jj采纳,获得10
2秒前
充电宝的应助被果果采纳,获得10
2秒前
傲柏完成签到 ,获得积分10
2秒前
2秒前
leo完成签到,获得积分20
4秒前
dgb发布了新的文献求助10
4秒前
闪闪谷雪完成签到,获得积分10
4秒前
幻涯发布了新的文献求助10
5秒前
西柏发布了新的文献求助10
5秒前
finish发布了新的文献求助10
5秒前
5秒前
5秒前
小蘑菇的应助被彭雄兵采纳,获得10
5秒前
爱发呆的同学完成签到,获得积分10
6秒前
7秒前
谨岛嗦关注了科研通微信公众号
7秒前
充电宝的应助被鲸落采纳,获得10
7秒前
orixero的应助被ceruelan采纳,获得10
7秒前
Jade0259完成签到 ,获得积分10
8秒前
哆啦发布了新的文献求助10
8秒前
8秒前
9秒前
NAN完成签到,获得积分10
9秒前
隐形曼青的应助被酷酷柚子采纳,获得10
9秒前
烟花的应助被dgb采纳,获得10
9秒前
阑楚发布了新的文献求助10
10秒前
乐观荔枝发布了新的文献求助10
10秒前
10秒前
初景发布了新的文献求助10
11秒前
斯文败类的应助被策略采纳,获得10
11秒前
王世缘完成签到,获得积分10
12秒前
12秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
Grapes 1000
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8178280
求助须知:如何正确求助?哪些是违规求助? 9569046
关于积分的说明 21802436
捐赠科研通 7773138
什么是DOI,文献DOI怎么找? 3432735
关于科研通互助平台的介绍 2556770
邀请新用户注册赠送积分活动 2478274