论文部分内容阅读
论文首先给出了时间自动机的定义及相关符号，然后对使用等价类方法构造区域自动机的描述进行了算法实现。该算法的空间复杂度是状态数目的几何级扩张。对上述算法做进一步改进，使得平均时间复杂度有所改善。通过分析时间自动机的时间约束条件，又提出了一种新的构造区域自动机的算法，该算法的时间复杂度与空间复杂度都有了较大的改善。接着介绍了时间自动机的最新进展，即有关事件记录自动机，事件预测自动机以及事件时钟自动机。对上述自动机的有关性质及它们所识别的语言类之间的关系进行了研究，得出一些有益的结论。论文最后给出了一个使用时间自动机的验证实例。