袋自动机

提出了袋自动机模型和袋语言的概念,并给出了袋自动机的状态转换图;分析了袋语言重复序列在状态转换图中的反映,并划分为不变重复序列、增重复序列、减重复序列和传递重复序列,给出了袋语言的结构特性;研究了袋语言类同Chomsky文法体系中各型语言的关系,证明了正规语言类是袋语言类的真子集,袋语言类是上下文有关语言类的真子集,而袋语言类同上下文无关语言类是两个相交但互不包含的语言类,即存在不是上下文无关语言的袋语言,也存在无法用袋自动机产生的上下文无关语言.     

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。     

基于量子逻辑的下推自动机与上下文无关文法

给出基于量子逻辑的下推自动机(e-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的e-VPDA与状态转移为分明函数且具有量子终态的e-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(e-VCFG)的等价性.     

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。     

上下文无关语言的同步运算及其性质

针对上下文无关语言,引入了语言的可重复序列的依赖运算和同步运算,分析了两种运算的性质、特点,给出了可重复序列的依赖表达式、同步串约束表达式;提出了同步串约束上下文无关语言,给出了该类语言的构造规则:对于字母表上的同步串约束上下文无关语言L,都是由该字母表上的一个正规语言R与该正规语言R中某些可重复序列之间的依赖约束所形成的;证明了同步串约束上下文无关语言与同步串约束表达式所描述的语言等价,且该类语言是上下文无关语言的真子集.     

下推自动机的状态转换图与下推自动机的化简

参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。     

二元文法

在正规文法的基础上,通过增加一个约束变量集合,给出了二元文法的定义,证明了二元文法与袋自动机的等价性,定义了平衡推导、递增推导、递减推导和传递推导,证明了它们与不变重复序列、增重复序列、减重复序列和传递重复序列之间的关系,并且给出判定一个二元文法所产生语言（袋语言）分别是正规语言、上下文无关语言或上下文文有关语言的充分条件。     

基于量子逻辑的下推自动机的代数刻画

首先,本文提出量子下推自动机（简记为L-VPDA）的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA间的相互等价性;其次详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。     

Petri网的状态转换图

给出Petri网的状态转换图模型,并作为分析工具,分析Petri网重复引发序列在状态转换图中的表现特点,给出标注路径(回路)与引发序列(重复引发序列)的关系及其判定条件,并给出求基本重复引发序列的计算方法;定义了可重复序列之间的依赖性和依赖度,准确地给出了可重复序列之间依赖关系的形式描述;分析了Petri网语言的结构特点,证明了任意一个Petri网语言都是一个正规语言表达式与该网的可重复引发序列α闭包的同步.     

论回溯自动机

为了描述集成化软件工程环境用户接口中选单的控制机构,需要引入回溯自动机的概念。本文给出了回溯自动机概念的严格数学定义,并讨论了它与有穷自动机、确定的下推自动机等之间的关系,证明了它所接受的语言类处于正则语言类与确定的上下文无关语言类之间。     

顺序图与状态图的递归语义一致性研究

建模面向对象的软件系统是UML的动态图的重要应用,采用顺序图描述消息传送,动态图描述活动.在大型系统开发过程中,往往存在大量顺序图和状态图,由于语义的缺失,导致这些图形表达涵义模糊不清,特别是在递归的信息传送上,由于表达方式的特点,状态图很容易造成实现过程的歧义甚至死锁.提出了基于ASM的多agent实时控制方法,结合形式化的规则定义,通过多个层次agent控制状态的跃迁,保证状态图在描述复杂信息传送时,能够和顺序图的时序保持一致,这对提高系统的可靠性具有一定的现实意义.     

基于UML与有色Petri网的RBC切换场景的建模方法研究

针对仅有一台车载电台正常的RBC(无线闭塞中心)切换场景,探讨了一种基于UML模型和有色Petri网(CPN)的系统建模方法;首先利用UML模型的顺序图及状态图描述RBC切换流程和过程中车载设备的状态转移,再从UML状态图中提取信息构造相应的有色Petri网模型,最后利用CPN Tools的状态空间工具分析模型的有界性、家态性、活性和公平性,得到的模型动态行为符合RBC切换功能的要求;论文验证了该建模方法的有效性,为完善RBC系统设计提供依据。     

用STATECAD快速设计有限状态机

有限状态机设计的关键是如何把一个实际的时序逻辑关系抽象成一个时序逻辑函数,传统的电路图输入法通过直接设计寄存器组来实现各个状态之间的转换,而用硬件描述语言来描述有限状态机,往往是通过充分发挥硬件描述语言的抽象建模能力,通过对系统在系统级或寄存器传输级进行描述来建立有限状态机。随着EDA工具的快速发展,通过CAD快速设计有限状态机自动化成为可能。     

基于Time Petri Nets的UML时序图分析

引入一种称为Clock的变迁,用来改进TPNs,讨论了如何将时序图转换为基于Clock变迁的TPNs,使这种TPNs能正确反映时序图的流程和时间约束。最后,利用普通Petri网的可达性分析技术对时序图模型进行了分析和验证。     

二叉树型结构的细胞自动机同构性构造

用状态转移矩阵方程表示加性细胞自动机的状态转移,通过状态转移矩阵及其特征多项式来分析加性细胞自动机的状态转移特性,从而求出其状态转移图.2k-1单元的零边界90线性细胞自动机的状态转移矩阵的秩为2k-2,从而可以确定其状态转移图具有二叉树型结构.同时,根据其状态转移矩阵方程可以求出2k-1单元的零边界90线性细胞自动机对应的22k-1个2k-1单元的零边界90加性细胞自动机具有相同的状态转移结构,即这22k-1个90加性细胞自动机同构.这样可系统构造一簇具有相同二叉树型状态转移结构的细胞自动机.     

基于状态图的测试路径自动生成

提出一种基于状态图的测试路径自动生成算法,该算法从状态图的初始状态到终止状态进行遍历,可以得到一组路径,由该组路径生成的测试用例集可满足状态图的转移覆盖测试准则。根据循环复杂度,对路径集的总长度进行优化,从而减少测试用例数量。实验结果表明,该算法有效可行,在实际应用中能够取得良好的效果。     

基于状态转换的Web程序测试方法研究

基于状态转换的测试方法是探测Web程序动态行为异常的有效途径。Web程序状态的变迁由链接序列和提交数据共同构成的导航场景决定。本文用活动页面导航图(APND)来描述页面间的链接转换行为,用状态变量的组合对象状态图(COSD)来刻画由提交数据导致的系统状态变量改变,再将两者统一成一个较为全面的动态行为模型Web程序状态转换图(WSTD)。最后,采用线索k叉树并加以改造来自动生成测试用例。     

基于UML状态图的类测试用例实现的研究和设计

UML状态图能有效的表现系统的并发控制和类的嵌套,但用其实现的类测试用例复杂.研究了UML状态图和扩展有限状态机这两种方法在软件测试中状态转换的特点,利用扩展有限状态机状态转换单一线索化的特点降低UML状态图在类测试用例生成中的复杂性.以一个坐标图形显示类的测试用例生成为例,详细讨论了结合扩展有限状态机状态转换特点的UML状态图在面向对象测试技术中的应用.