一类交替的ω—有穷自动机和确定的ω—有穷自动机识别能力…

本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机，并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。     

一种新的ω－识别模型

本文提出了一种新的ω－识别模型：ω－循环自动机及其循环接受条件．给出了ω－循环自动机在该接受条件下所接受的ω－语言类的集合表示．     

关于ω—有穷自动机的两个新的接受条件

至今被公开的ω有穷自动机的接受条件有６个即Ｃ１－Ｃ６，寻找新的接受条件和研究ω－有穷自动机关于新接受条件接受ω－语言能力是ω有穷自动机理论中的一个重要课题。本定义了ω有穷自动机的两个新的接受条件Ｚ１和Ｚ２，并且研究了：（１）ω－Ｕ－ＮＦＡ关于Ｚｉ（ｉ＝１，２）接受ω－语的能力。     

关于交替的ω─有穷自动机的接受条件

到目前为止，交替的ω－有穷自动机的接受条件仅有６种，本文给出了６种新形式的接受条件，并研究了交替的ω－有穷自动机在这些条件下识别语言的能力．最后给出了ω－自动机在各种接受条件下识别的语言类．     

一类交替的ω－有穷自动机和确定的ω－有穷自动机识别能力的等价性

本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机（记为ω－ＵＡＦＡ），并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。     

关于交替的ω—有究自动机的接受条件

到目前为止，交替的ω－有究自动机的接受条件仅有６种，本给出了６种新形式的接受条件，并研究了交替的ω－有究自动机交些条件下识别语言的能力，最后给出了ω－自动机在各种接受条件下识别的语言类。     

ω—正则语言类的一个子类

ω－语言是由有穷字线靖Σ上的一些无穷串组成的集合，被ω－有穷自动机接受的ω－语言称为ω－正则语言，作者曾从集合的角度描述了一类ω－正则语言，而不是传统地从生成或识别的角度来描述这一类正则语言，本文从集合的角度来描棕更为广泛的一类ω－正则语言。     

一类ω—正则语言

ω—语言是由有穷字母表∑上的某些无穷串组成的集合。被所谓的ω—有穷自动机接受的ω—语言称为ω—正则语言。在[4]中作者曾从集合的角度给出—ω—语言为ω—正则语言的几个充分条件。在本文作者仍从集合的角度给出一个ω—语言为ω—正则语言的充分条件,即若—ω—凸语言L满足L=adh(pref(L))=pref(L)tail(L),则L是—ω—正则语言。从而,确定了ω—正则语言类的一个子类。     

ω幂上下文无关语言及其封闭性质

本定义了ω幂上下无关语言ω－ｐ－ｃｆｌ和一类ω下推自动机ω－ｐｄａ，给出了它们的关系，借助于ω时序转换器ω－ＳＴ，讨论了ω－ｐ－ｃｆｌ类的某些封闭性质，证明了对于ω－ｐ－ｃｆｌ类ζ，ξ（δ）＝｛Ｓ（Ａ）｜Ａ∈ζ，Ｓ是一个ω－ＳＴ｝＝｛ｈ２（ｈ＾－１１（Ａ）∩Ｒ）｜Ａ∈ξ，Ｒ是一个ω正规语言，ｈ１是一个同态，以及ｈ２是一个λ无关同态｝。     

S广义ω—凸语言

本文通过在∑＾ω上定义半序关系“≤ω＾ｓ”，引进Ｓ广义ω－左凸语言，Ｓ广义ω－右凸语言和Ｓ广义ω－凸语言的概念，并给出各类Ｓ广义ω－凸语言与其前缀语言之间的关系；还给出了各类Ｓ广义ω－凸语言族对布尔运算的封闭性以及各类Ｓ广义ω－凸语言的充分必要要条件。     

关于有ω-穷自动机的两个新的接受条件*

至今被公开的ω-有穷自动机的接受条件有6个即C₁—C₆，寻找新的接受条件和研究ω-有穷自动机关于新接受条件接受ω-语言的能力是ω-有穷自动机理论中的一个重要课题．本文定义了ω-有穷自动机的两个新的接受条件Z₁和Z₂，并且研究了：(1)ω-U—NFA关于Z_i(i=1,2)接受 ω-语言的能力，得到了 N     

循环自动机的等价性

主要讨论了两个循环有限自动机的等价性与循环有限自动机的生成子之间的关系,在某些条件下给出了两个循环有限自动机等价的充分必要条件。     

几类ω—凸语言族的分层

本对作几年来先后在ω－语言族中定义的五类ω－凸语言进行了相应的分层。     

Streett自动机确定化工具

自动机的确定化是将非确定性自动机转换为接收相同语言的确定性自动机,是自动机理论的基本问题之一.ω自动机的确定化是诸多逻辑,如SnS, CTL*,μ演算等,判定过程的基础,同时也是解决无限博弈求解问题的关键,因此对ω自动机确定化的研究具有重要意义.主要关注一类ω自动机——Streett自动机的确定化.非确定性Streett自动机可以转换为等价的确定性Rabin或Parity自动机,在前期工作中已经分别得到了状态复杂度最优以及渐进最优算法,为了验证提出的算法的实际效果,也为了形象地展示确定化过程,开发一款支持Streett自动机确定化的工具是必要的.首先介绍4种不同的Streett确定化结构:μ-Safra tree和H-Safra tree (最优)将Streett确定化为Rabin自动机, compact Streett Safra tree和LIR-H-Safra tree (渐进最优)将Streett确定化为Parity自动机;然后,根据Streett确定化算法,基于开源工具GOAL (graphical tool for omega-automata and logics),实现...     

一种基于自动机理论的LTL检验符号优化方法

模型检验是一种重要的形式化自动验证技术。检验一个模型是否满足LTL公式,可以把LTL公式转换为一个表示相同无穷状态序列的ω自动机,通过转换后的ω自动机与系统自动机的乘积判空来进行模型检验。由于自动机的体积是模型检验的一个关键性问题,为了得到尽可能小的自动机,在LTL公式转换为ω自动机之前,对LTL公式进行预处理来减少冗余,然后基于ROBDD,通过布尔技术优化自动机。     

ω-NTB文法及其秩的若干性质

本文引入了ω-HTB文法及其秩的概念,证明了ω-HTB语言和ω超线性语言是同一语言类,给出了ω-NTB文法秩的若干重要性质。     

离散事件动态系统的D－B动机模型

首先引入Ｄ－子集和Ｄ－语言的概念，在此基础上给出了一类离散事件动态系统的一般形式化表述──Ｄ－自动机模型，并讨论了受控系统的动态行为．最后研究了系统的状态可达性问题．     

二元弱可逆有限自动机延迟步数的分解

本文考虑二元严格延迟τ步弱可逆有限自动机Ｍ的延迟步数的分解问题。首先证明如果Ｍ强连通且所有状态的延迟步数不小于τ－１，则Ｍ一定能分解为一个延迟０步弱可逆有限自动机和一个τ阶延迟元。然后证明如果Ｍ所有状态延迟步数均不小于ｍ，那么Ｍ可以分解为一个严格延τ－ｍ步弱可逆有限自动机和一个ｍ阶延迟元。最后考虑了Ｍ可分解为一个严格延迟τ－１步和一个严格延迟１步弱可逆有限自动机的条件。     

多带自动机在YH—F2算术表达式并行编译中的应用

本文结合ＹＨ－Ｆ２系统的并行运算机制，分析了算术表达式的标量并行计算机方法，指出传统单带自动机编译算法在识别全局并行性的不足，提出了一种基于多带自动机的编译方法，对表达式的全局并行计算进行局部关联。     

论回溯自动机

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