时间自动机可达性分析中的状态空间约减技术综述

时间自动机是检验实时系统建模的有效工具，其可达性分析可以检验系统是否可能达到某些特定的状态，其算法通常采用对符号状态的枚举来遍历其状态空间。因为引入了时钟变量，时间自动机的可达性分析算法会产生大量的中间状态，需要巨大的存储空间，往往超出了计算机能力的极限，导致分析和检验不能完成。这就是所谓的“状态空间爆炸”。研究人员设计了很多种优化技术来约减可迭性分析所需的存储空间，以解决或者缓解这个问题。本文首先介绍了时间自动机及其可达性分析的基本概念，然后分类讨论了现有的空间约减优化技术并对此做出总结，最后提出了一些