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

伪半环及其在自动机理论中的应用

作　者: 李平
导　师: 李永明
学　校: 陕西师范大学
专　业: 基础数学
关键词: 伪半环 伪加权有穷自动机 伪加权语言 等价 伪加权传感器 实现化 伪加权图灵机 通用性
分类号: TP301.1
类　型: 博士论文
年　份: 2010年
下　载: 49次
引　用: 0次
阅　读: 论文下载
 

内容摘要


加权有穷自动机是经典的非确定有穷自动机的转移附加上权重,这些权重通常做成一个代数结构-半环.取值于半环的加权有穷自动机的理论研究及其实际应用都已经得到了很好的阐述.最近,不少作者发现自动机的权重可以作成更广泛的代数结构-伪半环(也叫做强双半群),即半环去掉分配律形成的代数结构.半环、格半群、完备正交模格都是伪半环的特例.Manfred Droste教授在他的两篇文章中给出了三种语义下伪加权有穷自动机(也称作强双半群上的加权有穷自动机,简记为P-NFA)所识别的语言,并分别研究了伪加权有穷自动机的一些性质及其确定化.本文进一步研究伪加权有穷自动机的其它性质.本文的主要工作主要有以下几个方面：(1)在七种不同语义下,研究了各类型的伪加权有穷自动机的关系.首先介绍了偏序伪半环、正序伪半环、伪加权子集、伪加权矩阵的概念.其次,论文在已有的三种语义基础上增加了四种新的语义,得到了七种语义,它们分别是初始代数语义(I)、终止代数语义(F)、初始转移语义(IT)、终止转移语义(FT)、初始混合语义(IH)、终止混合语义(FH)、运行语义(R).引入了左等价、右等价、M-右等价、等价、右等价-、M-右等价-ε、等价-ε的概念(其中,φ≠M∈{I,F,IT,FT,TH,R}),利用这些概念,在七种语义下详细讨论了四类型非确定型伪加权有穷自动机P-NFA1,P-FA2,P-FA3,P-FA4之间的关系,以及三类型确定型伪加权有穷自动机P-DFA1,P-FA2,P-FA3之间的关系.得到了完整的结论.最后,介绍了七种语义下伪加权有穷自动机的反转的一些性质.(2)研究了几类带有输出的伪加权有穷自动机的性质.文章给出了几种常见的带输出的伪加权有穷自动机,它们分别是：伪加权转换器、伪加权同步机、伪加权序列机、伪加权Mealy机、伪加权Moore机.并给出了伪加权转换器的延迟函数的实现化、伪加权转换器的输出函数及输入函数的实现化、伪加权转换器的极小确定实现化、伪加权同步机的单转移实现化；借助于伪加权序列机,证明了伪加权Mealy机与伪加权Moore机是不等价的.(3)研究了伪加权图灵机的一些性质.在深度优先和宽度优先意义下,首先讨论了非确定型伪加权图灵机P-TM与带有分明移动的伪加权图灵机P-TMc的关系、带有分明移动的伪加权图灵机P-TMc与确定型伪加权图灵机P-DTM的关系.证明了P-TM与P-TMc不论在深度优先还是在宽度优先意义下都是不等价的,但P是乘法局部有限时二者在深度优先意义下是等价的；P-TMc与P-DTM也是不等价的,甚至在P是加法局部有限时,二者也不等价,但当P是偏序伪半环时,作为有限伪加权递归语言的识别器二者又是等价的.其次讨论了伪加权图灵机的通用性.证明了在P有限时,通用P-TM(P-TMc)与通用P-DTM都是存在的；当伪半环P无限时,通用P-DTM不存在.

全文目录


摘要  3-5
Abstract  5-9
前言  9-15
第1章 预备知识  15-29
  1.1 伪半环的概念及其基本性质  15-19
  1.2 伪加权子集及其基本性质  19-22
  1.3 取值于伪半环的矩阵及其运算  22-29
第2章 伪加权有穷自动机  29-61
  2.1 伪加权有穷自动机的概念及其所识别的语言  29-32
  2.2 伪加权有穷自动机的类型  32-35
  2.3 不同语义下四类型非确定型伪加权有穷自动机的关系  35-49
  2.4 不同语义下三类型确定型伪加权有穷自动机的关系  49-55
  2.5 不同语义下伪加权有穷自动机的反转及其性质  55-61
第3章 带输出的伪加权有穷自动机  61-87
  3.1 伪加权转换器及其延迟函数的实现化  61-66
  3.2 伪加权转换器的输入函数及输出函数的实现化  66-71
  3.3 伪加权转换器的极小确定实现化  71-76
  3.4 伪加权同步机的单转移实现化  76-81
  3.5 伪加权Mealy机与伪加权Moore机的关系  81-87
第4章 伪加权图灵机及其通用性  87-113
  4.1 伪加权图灵机的概念及其基本性质  87-98
  4.2 有限伪加权递归可枚举语言及递归语言的层次刻画  98-106
  4.3 伪加权图灵机的通用性  106-113
总结  113-115
参考文献  115-121
致谢  121-123
攻读博士学位期间的研究成果  123

相似论文

  1. 铁皮石斛叶绿体微卫星的开发应用及其种间通用性研究,S567.239
  2. 广义系统的结构分析及控制方法研究,N945.1
  3. 一些亏损更新方程解渐近等价的条件,O211.67
  4. 一种FFTT非对称加解密算法的研究与实现,TP309.7
  5. 交通肇事逃逸致人死亡定罪研究,D924.3
  6. 基于模糊理论的Web用户聚类的研究,TP311.13
  7. Jacket矩阵的性质与构造,O151.21
  8. 参数化产品族定位优化方法研究,TB472
  9. 基于事物特性表的零件族建模方法研究与应用,TP391.72
  10. 关于夏目漱石作品中的金钱,I313.074
  11. 场地中软夹层对地震动的影响,TU435
  12. 相关稳健估计在GPS数据处理中的应用研究,P228.4
  13. 非等价加工圆柱凸轮廓面误差的试验研究,TH132.47
  14. 基于二进制代码等价变换的代码伪装技术研究,TP393.08
  15. 多源二进制代码一体化翻译关键技术研究,TP391.2
  16. 排课系统的设计与实现,TP311.52
  17. 面向自适应中间件的语义构件动态组合研究与应用,TP311.52
  18. 基于进程演算的公钥密码体制自动化安全性证明方法研究,TN918.1
  19. 基于流量均衡的路由优化问题研究,TN915.02
  20. 基于EOS芯片MAC模块的EDA验证,TN402
  21. 逆半环上同余的刻画,O153.3

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 自动机理论
© 2012 www.xueweilunwen.com