共查询到20条相似文献,搜索用时 31 毫秒
1.
ω-语言是由有穷字线靖Σ上的一些无穷串组成的集合,被ω-有穷自动机接受的ω-语言称为ω-正则语言,作者曾从集合的角度描述了一类ω-正则语言,而不是传统地从生成或识别的角度来描述这一类正则语言,本文从集合的角度来描棕更为广泛的一类ω-正则语言。 相似文献
2.
关于ω—正则语言类的一个子类的特征 总被引:1,自引:0,他引:1
为了给出本文的主要结果,首先引进了由有穷字母表∑上的ω~-语言所确定的集合∑~ω上的ω-Nerode等价关系的概念.在此基础上证明了∑上的与前缀逆相关的ω~-语言是ω~-正则语言,当且仅当由它所确定的ω-Nerode等价关系的指数有穷.从而,本文从代数、集合的角度给出了在∑上的与前缀逆相关的一类ω~-语言中,ω~-正则语言的特征. 相似文献
3.
4.
本文定义了ω幂上下文无关语言ω—P— cfl和一类ω下推自动机ω—pda,给出了它们
的关系.借助于ω时序转换器ω—ST,讨论了ω—p—cfl类的某些封闭性质,证明了对于ω—p—cfl类L,m(L)={s’(A)|A∈s'是一个ω—ST)=(h2(h1-1(A)∩R)|A∈L,R是一个ω正规语言,h1相似文献
5.
关于有ω-穷自动机的两个新的接受条件* 总被引:1,自引:0,他引:1
至今被公开的ω-有穷自动机的接受条件有6个即C1—C6,寻找新的接受条件和研究ω-有穷自动机关于新接受条件接受ω-语言的能力是ω-有穷自动机理论中的一个重要课题.本文定义了ω-有穷自动机的两个新的接受条件Z1和Z2,并且研究了:(1)ω-U—NFA关于Zi(i=1,2)接受 ω-语言的能力,得到了 N 相似文献
6.
苏锦祥 《计算机研究与发展》1985,(4)
ω-语言是有穷字母表(sum from)上的无穷串所构成的集合,被工作在无穷串上的所谓的ω-有穷自动机接受的ω-语言称为ω-正则语言.[1]中给出的关于ω-正则语言的一些条件,是由ω-有穷自动机与ω-右线性文法描述的.本文通过在(sum from)上的一切ω-字组成的集合(sum from)~ω上引进的二元关系"≤ω",定义了ω-左凸语言和ω-右凸语言.从而利用ω-语言的ω-左凸性质、ω-右凸性质,从集合的角度给出了ω-语言是ω-正则语言的几个充分条件.主要结果是:若一个(sum from)上的ω-语言L是闭的且L/(sum from)~ω是(sum from)上的正则集,则L是(sum from)上的ω-正则语言;若一个(sum from)上的ω-语言是闭的ω-左凸语言,则它是ω-正则语言;若一个(sum from)上的ω-语言是闭的ω-右凸语言,则它是ω-正则语言. 相似文献
7.
8.
9.
相应于无冲突依赖的规范化对象模式森林 总被引:2,自引:1,他引:2
首先概括对象依赖、无冲突对象依赖集合、规范化对象模式森林和复杂对象模式规范化设计算法的基本概念和性质;然后给出并证明相应于无冲突对象依赖集合M的规范化对象模式森林F的性质:P(F)是惟一的、不可分解的规范化对象模式森林的路径集合;M<=>OD(F)<=>P(F);P(F)是无(环的.这对于面向对象信息系统的开发有一定的意义. 相似文献
10.
Pawlak教授提出的粗糙集理论是解决集合边界不确定的重要手段,他构建了边界不确定集合的两条精确边界,但没有给出用已有知识基来精确或近似地构建目标概念(集合)X的方法.在前期的研究中提出了寻找目标概念X的近似集方法,但并没有给出最优的近似集.首先,回顾了集合间的相似度概念和粗糙集的近似集Rλ(X)的构建方法,提出并证明了Rλ(X)所满足的运算性质.其次,找到了Rλ(X)比上近似集R(X)和下近似集R(X)更近似于目标概念X的λ成立的区间.最后,提出了R0.5(X)作为目标概念的最优近似集所满足的条件. 相似文献
11.
12.
13.
合取范式(CNF)公式H到F的同态φ是一个从H的文字集合到F的文字集合的映射,并保持补运算和子句映到子句.同态映射保持一个公式的不可满足性.一个公式是极小不可满足的是指该公式本身不可满足,而且从中删去任意一个子句后得到的公式可满足.MU(1)是子句数与变元数的差等于1的极小不可满足公式类.一个三元组(H,φ,F)称为的一个来自H的同态证明,如果φ是一个从H到F的同态.利用基础矩阵的方法证明了:一个不可满足公式F的树消解证明,可以在多项式时间内转换成一个来自MU(1)中公式的同态证明.从而,由MU(1)中的公式构成的同态证明系统是完备的,并且由MU(1)中的公式构成的同态证明系统与树消解证明系统之间是多项式等价的. 相似文献
14.
模糊语言的研究是形式语言研究的焦点之一,然而如何对模糊语言进行刻画甚至更好地分类是其中一个重要研究方向.文章在模糊ω-语言的研究基础上,从模糊逻辑角度研究了模糊ω-正则语言的等价刻画.首先借助广义子集构造方法,证明了任一模糊Büchi自动机与具有分明初始状态和状态转移函数且具有模糊终状态的模糊Büchi自动机是等价的,藉此研究了模糊ω-正则语言的代数刻画和层次刻画,讨论了模糊ω-正则语言关于正则运算的封闭性;其次引入单体二阶(L)ukasiewicz逻辑的概念,给出模糊Büchi自动机识别语言的等价逻辑刻画;最后通过引入ω-星自由和ω-非周期模糊ω-语言,利用“层次化”处理技巧得到了多值逻辑意义下的分类定理,对模糊ω-正则语言给出了一种分类方法. 相似文献
15.
加权3-Set Packing 的改进算法 总被引:1,自引:0,他引:1
Packing 问题构成了一类重要的NP 难问题.对于加权3-Set Packing 问题,把问题转化成加权3-Set Packing
Augmentation 问题进行求解,即主要讨论如何从一个已知的最大加权k-packing 求得一个权值最大的(k+1)-packing.
通过对问题结构的分析,结合Color-Coding 技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing 结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k). 相似文献
16.
考虑有限域上椭圆曲线的构造.设q是一个奇素数的方幂,l是一个素数.证明了,如果GF(q)[x]上的方程U2-D(x)V2=ε(x-a)l有本原解,其中,D(x)∈GF(q)[x]是一个首1三次无平方因子的多项式,则椭圆曲线y2=D(x)上的点(a,b)的阶是l.由此,给出了一种构造具有给定阶点的椭圆曲线的算法. 相似文献
17.
有中断时间代价的一致并行机抢先调度问题 总被引:1,自引:0,他引:1
提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|Cmax的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2. 相似文献
18.
Recently, it is proved in the literature that for a given
controllable pair (A,B) with A∈Rn*n,
B∈Rn*m, and any λ≥1,a gain
matrix K can be designed so that ‖e(A+BK)t‖≤MλLe-λt,where M and L are constants
independent of λ.Here, we show that M and L can be
chosen much smaller than that proposed above. As a consequence, the
estimation on overshoot of a transition matrix can be bounded more
precisely. This can be regarded as a complement to the existing
result. 相似文献
19.
本文提出了一类交替的ω-有穷自动机,即所有状态都是万能的交替的ω-有穷自动机,并采用了构造的方法证明了ω-UAFA和确定的ω-有穷自动机在四种接受条件下接受的ω-语言的等价性。 相似文献
20.
本文对使用C语言设计多窗口编辑,以实现Foxbase的@get-read功能为例,介绍curses函数的用法,并给出了源程序。 相似文献