学位论文 > 优秀研究生学位论文题录展示

加权Moore机的同余与格值Moore机的约化

作　者: 李苏妮
导　师: 李永明
学　校: 陕西师范大学
专　业: 基础数学
关键词: 加权Moore机格值Moore机同余约化最小化算法
分类号: TP301.1
类　型: 硕士论文
年　份: 2011年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

自动机理论论述了计算的数学模型,它是算法描述和分析、计算复杂性理论、可计算性理论等研究的基础,它为计算理论提供了可靠的数学模型.加权自动机是带有权重的非确定型自动机,这些权重可以代表自动机运行中的费用,资源的消耗、时间、成功运行的概率或可靠性.加权自动机在计算机科学领域有重要的理论和实际应用,包括经典自动机的代数化处理、自然语言处理、语言识别、数字图像压缩等方面.本文在加权自动机理论的基础上,详细研究和讨论了加权Moore机的同余和最小化问题,及格值Moore机的约化等问题.本文的主要工作如下：1.在加权自动机理论的基础上,研究了加权Moore机的一些重要性质,T.Petkovic运用代数理论方法研究了模糊自动机,讨论了模糊有穷自动机的同余同态.作为扩张,本文首先定义了加权Moore机的同余与同态,给出了联系同余和同态关系的同态定理,其次,证明了同余关系在加权Moore机中构成一个完备格,最后,在同余关系下给出了加权Moore机的商Moore机,并给出了求最小状态Moore机的算法.2.提出了基于完备剩余格的Moore机(简称格值Moore机)的形式化定义,详细讨论了格值Moore机的一系列性质,给出了格值Moore机与它的商格值Moore机等价的条件.再定义了格值Moore机的右不变模糊等价关系,论述了右不变模糊等价关系具有一般性,证明了格值Moore机的同余关系只是格值Moore机右不变模糊等价关系的一种特殊情形.同时,讨论了右不变模糊等价关系在格值Moore机中可以构成一个完备格.进而,在格值Moore机中就存在最大的右不变模糊等价关系,为格值Moore机在右不变模糊等价关系下具有最小化提供了理论依据.最后,给出了求最大格值Moore机右不变模糊等价关系的算法和示例.类似地，我们给出了左不变模糊等价关系的定义及求最大左不变模糊等价关系的算法.对于一个格值Moore机,对它进行右约化后就不能再进行进一步的约化了,然而,它还可以进行左约化.在对一个格值Moore机的交替约化进行了有限步后,这个格值Moore机的状态数不再减少,即为状态数的最小化.最后,举例验证了左右交替约化和右左交替约化下得到的格值Moore机的状态数是不同的,并且左右交替约化和右左交替约化的长度也是不同的.

全文目录

摘要  3-4
Abstract  4-7
前言  7-9
第1章预备知识  9-17
  1.1 半群与半环  9-10
  1.2 格与模糊集  10-13
  1.3 模糊关系与矩阵  13-17
第2章加权Moore机的同余与最小化  17-27
  2.1 加权Moore机  17
  2.2 加权Moore机的同余与同态  17-23
  2.3 加权自动机的同余与最小化  23-27
第3章格值Moore机的约化  27-41
  3.1 基本概念  27-30
  3.2 格值Moore机的右不变模糊等价关系  30-35
  3.3 格值Moore机的左不变模糊等价关系  35-38
  3.4 格值Moore机的左约化右约化及交替约化  38-41
结论  41-43
参考文献  43-47
致谢  47-49
攻读硕士学位期间科研成果  49

加权Moore机的同余与格值Moore机的约化

内容摘要

全文目录

相似论文