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

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

关于ω—正则语言类的一个子类的特征

为了给出本文的主要结果,首先引进了由有穷字母表∑上的ω~-语言所确定的集合∑~ω上的ω-Nerode等价关系的概念.在此基础上证明了∑上的与前缀逆相关的ω~-语言是ω~-正则语言,当且仅当由它所确定的ω-Nerode等价关系的指数有穷.从而,本文从代数、集合的角度给出了在∑上的与前缀逆相关的一类ω~-语言中,ω~-正则语言的特征.     

一类ω—正则语言

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

关于ω-语言的正则性

本文给出某些类ω-正则语言的某些代数描述。用∑~ω表示字母表∑上的一切ω-字的集合。设σ=a_1…a_n…,令σ(n)=a_1…a_n。在∑~ω上定义二元关系“≤_ω”:对σ_1,σ_2∈∑~ω,σ_1≤_ωσ_2当且仅当σ_1=x_1…x_n…,σ_2=y_1x_1y_2…x_ny_(n 1)…,x_1,y_i∈∑~ω。 定义1.对σ_n∈∑~ω,n=1,…,若存在σ∈∑~ω,使σ_n(n)=σ(n),n=1,…,则称σ是序列{σ_n)的极限。     

3型语言类对S-映射的封闭性

形式语言理论的问题之一是对各种语言类在各种运算和映射之下的封闭性的研究。 本文定义了一种从一有穷非空字母表V的闭包V到一有穷非空字母表W的闭包W的幂集2的S-映射,从而,给出了3型语言类对S-映射封闭的两种证明。 从V到2~W的映射σ称为S-映射当且仅当σ是一个从V到2~W的置换,使得集族 {σ(x)|x∈V}构成集合W的一个分划。     

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

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

一个基于实化聚集视图的近似查询计算模型及其应用

在数据仓库、大量交易记录系统、移动计算、联机分析处理系统(OLAP)等许多领域中聚集数据的处理是一个非常重要的核心问题。该文首先分析了聚集数据查询的特点,引入了聚集查询语言和聚集查询重写;其次对于聚集查询环境下如何实现快速查询,给出了一个基于聚集数据的近似查询计算模型;最后将该计算模型应用于人口统计系统,从而实现对统计信息类数据进行快速的查询处理,获得有效的查询结果。     

几类ω—凸语言族的分层

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

ω-正则语言族的几个子类

ω-语言是有穷字母表(sum from)上的无穷串所构成的集合,被工作在无穷串上的所谓的ω-有穷自动机接受的ω-语言称为ω-正则语言.[1]中给出的关于ω-正则语言的一些条件,是由ω-有穷自动机与ω-右线性文法描述的.本文通过在(sum from)上的一切ω-字组成的集合(sum from)~ω上引进的二元关系"≤ω",定义了ω-左凸语言和ω-右凸语言.从而利用ω-语言的ω-左凸性质、ω-右凸性质,从集合的角度给出了ω-语言是ω-正则语言的几个充分条件.主要结果是:若一个(sum from)上的ω-语言L是闭的且L/(sum from)~ω是(sum from)上的正则集,则L是(sum from)上的ω-正则语言;若一个(sum from)上的ω-语言是闭的ω-左凸语言,则它是ω-正则语言;若一个(sum from)上的ω-语言是闭的ω-右凸语言,则它是ω-正则语言.     

一种改进的区域自动机构造方法

用时间自动机验证一个有穷状态实时系统的正确性，可归结为判定两个时间正则语言的包含问题，亦可归结为判定两个时间正则语言的交是否为空的问题。在判定一个时间正则语言是否为空时，先要将时间自动机转化为无时间的区域自动机。Alur和Dill给出的构造区域自动机的算法，存在许多不可达或虽可达但无用的状态。通过对时钟约束进行分析，在求时钟区域和时间后继的过程中，不断地将一些不可达或无用状态筛掉，使构造出的区域自动机更为优化，改进了Alur等人给出的算法。