基于时间动态下推网络可达性分析

动态下推网络(DPN,Dynamic Pushdown Networks)由一组能刻画动态创建线程的动态下推系统(DPDS,Dynamic Push Down Systems)组成.本文首先将描述连续时间的实时时钟引入DPN,提出了时间动态下推网络(TDPN,Timed Dynamic Pushdown Networks),能对动态创建线程的实时并发递归系统建模;然后基于时钟关键点的时钟等价优化方法,并采用on-the-fly技术,仅关心栈顶及下一层的域状态转换,动态的将连续时间模型TDPN转换为时间域表示的离散模型DPN,同时给出TDPN到DPN的转换算法;最后证明在TDPN中的可达状态当且仅当其转换状态在DPN中可达,从而可解决带动态线程创建的实时并发系统的可达性分析.