非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

复杂性集类中的完全集问题

本文针对多项式时间多一归约、图灵归约及强图灵归约,探讨了一些复杂性集类存在完全集的充要条件,指出了此三种归约有表现在完全集上的差别.     

有穷长半模偏序集上的一个定理

本文是对参考文献[1]第二章定理14证明的补充和改进。该定理乃指: 定理14.在任何上(或下)半模的有穷长的偏序集内,Jordan-Dedekind链条件成立。 文献[1]中,考虑上半模情形,谈到已知一个连接链:γ∶a=x_0相似文献   

连接型自动机的极小化及其复杂性

通过定义确定型有穷自动机在状态集上的等价关系,可以构造一类非确定型有穷自动机在状态集上的等价关系,利用这个等价关系可以对这类非确定型有穷自动机进行极小化。     

赵青海:伊朗美国何以如此敌视

从若即若离到坚定盟友●:自上世纪70年代末伊朗伊斯兰革命以来,美国和伊朗就结下了死仇。但此前美伊关系却不是这样,一度甚至可称做“蜜月期”。■:了解了美伊关系60多年的沧桑变化,也许对我们透析当前伊核危机有所补益。今天美国人眼中的伊朗是“无赖国家”,是“邪恶轴心”之一;在伊朗人心里, 美国是其“头号敌人”,是“最大的     

关于确定有穷自动机最小化算法的注记

《程序设计语言编译原理》给出了确定有穷自动机(以下简称为DFA)最小化的算法.步骤1 构造DFA M 状态集S的分划Ⅱ.该分划是由若干个不相交的状态子集所组成,并且任何不同的两子集的状态都是可区别的,而同一子集中的任何两个状态都是等价的.其构造算法如下:BEGIN     

集对分析-可变模糊改进方法及其应用

为解决集对分析-可变模糊方法的不足,基于集对分析理论、可变模糊集理论及二元语义方法,提出集对分析-可变模糊改进方法.基于集对模糊联系度,构造相对隶属度矩阵,进而建立集对分析-可变模糊综合评价模型;结合评价等级特征值,运用二元语义方法确定评价等级和阈值;将该方法应用于道路交通安全评价问题.结果表明:集对分析-可变模糊改进方法在简化计算过程的前提下,所得评价结果与可变模糊方法、模糊模式识别方法及实际情况一致.     

书籍

<正>图灵的秘密作者:Charles Petzold图灵机是英国数学家阿兰·图灵提出的一种抽象计算模型,佩措尔德编著的《图灵的秘密:他的生平、思想及论文解读》深入剖析了图灵描述图灵机和可计算性的论文《论可计算数及其在判定性问题上的应用》。《图灵的秘密:他的生平、思想及论文解读》中在详解论文的同时,附带了大量的历史背景资料、图灵的个人经历,以及图灵机对人们理解计算机、人类意识和宇宙所产生的影响。     

2-Calabi-Yau三角范畴中的丛倾斜对象

在2-Calabi-Yau三角范畴中,几乎完备丛倾斜对象或几乎完备极大刚性对象T都存在两个补T1、T2.本文给出了T为几乎完备丛倾斜对象时满足⊥T［1］=add(T⊙T1⊙T2)的一个充要条件, 并将该充要条件推广到n丛范畴中的n丛倾斜对象. 另外, 本文证明了如果几乎完备极大刚性对象不是几乎完备丛倾斜对象, 那么⊥T［1］add(T⊙T1⊙T2)并进一步得到了极大刚性对象T是丛倾斜对象当且仅当⊥(T⊙T2)［1］(     

有限域上置换多项式的进一步研究

摘要:构造新的置换多项式是Lidl和Mullen在1988年提出的一个公开问题.当q~k≡2(mod 3)时,本文作者曾利用线性化多项式得到了有限域■上一类形如■的置换多项式.本文进一步得到了有限域■上形如■的置换多项式.     

关于联系系统横截（Transversal）理论的几个结果

本文引进了集对族■=<(x_i,y_i):i∈I>的横截概念。证明了■之所有部分横截的集合形成联系系统。这一结果与 Edmonds 和 Fulkerson 关于拟阵与横截的著名结果类似。本文还给出了■具有某种表示系统的充要条件、Hall定理(集对族情形)以及对称联系系统的 Rado 定理。     

关于“图灵归约”形式定义的一点注记

M.R.Garey和D.S.Johnson在[3]中引入“图灵归约”的概念,利用这个概念把NP完全性理论推广到包括组合最优化问题在内的更广的一类问题上。他们用oracle图灵机(OTM)模型给出了图灵归约的形式定义。但是,[3]中给出的这个形式定义是错误的。本文指出了这个错误并给出修正。     

幺半群-矩阵型自动机的商自动机

本文从两个幺半群之间的同态出发,构造(n,S)-自动机之间的满同态,得到自动机的同余关系,进一步,在状态集的商集上,重新构造新的自动机(即所谓商自动机),并阐述了所构造的自动机与满同态所对应的自动机是同构的.在此基础上,引入(n,S)-自动机上的所谓的■和■关系,证明了这两个关系是可交换的.     

最大度至多为3的图上极大分离集的最大数目

给定图G=(V,E),若顶点子集F在图G中的导出子图的最大度至多为1,则称F为图G的一个分离集;若F不是其他分离集的真子集,则称F为一个极大分离集。对极大分离集计数问题进行研究,证明了在所有n个顶点且最大度至多为3的图上最多有■个极大分离集,并刻画了相应的极图结构。     

■-知识与它的还原

利用单向S-粗集对偶,给出■-知识与■知识的F-还原概念,提出■-知识的F-还原定理与F-还原的属性补充冗余原理;单向S-粗集对偶是S-粗集的基本形式之一.     

有穷自动机状态极小化方法及正则语言判定优化

引入了等价性原则,定义等价关系的商集合∑*/～B,通过对商集合的有限性判断,来判定正则语言,大大简化了正则语言判定的步骤,并在有穷自动机的状态集上引入了等价关系,对等价状态进行压缩,构造出与其等价的最小有穷自动机,同时降低了有穷自动机状态的复杂性.     

正则语言非正则运算的封闭性

本文用构造的方法严格证明了识别正则语言三种非正则运算的确定型有穷自动机的存在性，进而得出正则语言类在非正则运算“∩”、“-”以及“ ”下的封闭性的结论，并具体给出识别三类语言运算的确定型有穷自动机模型．     

点谱充满实轴的自伴算子及其推论

<正>本文构造了一个无界自伴算子,其特征值是全体实数,通过Cayley变换后,得到了一个单位圆周上的点全为谱点且除点与1外全为点谱的西算子.于是,我们实际构造出了一个有界的线性算子,其正则集是一开集而不是区域,顺便,我们得到了一个定义在全直线上的抽象函数,它是严格增加及处处不连续的.     

平面上两个数字集生成的一类Moran测度的谱性

设■为任意扩张矩阵,■.该文通过构造一维2个数字集生成Moran测度的谱,得到了Moran测度■为谱测度的充要条件是a_n(n≥2)均为偶数,进一步给出了■的一类谱的结构.     

电脑能战胜人脑吗?

<正>今年6月8日,英国雷丁大学的几位研究人员宣称,"尤金·古斯特曼"软件通过了图灵测试,并称其为人工智能领域的一个"里程碑"事件。随后,一些媒体也按照"里程碑"的意义纷纷报道了这件事,但是引起很多人的疑问。为此,我们请教了中国科学院数学与系统科学研究院的陆汝钤院士等几位研究人员。测试结论是否靠谱?科学世界:在人工智能(AI)学界来看,英国研究者所称的"尤金软件通过了图灵测试"这件事,真的具有"里程碑"意义吗?陆汝钤:我个人感觉这种说法是不对的。他们作的这个结论并不符合图灵的原意。