| 【中文题名】 | 关于输入存贮线性有限自动机和状态机的研究 |
| 【英文题名】 | On Input-memory Linear Finite Automata and State Machines |
| 【学科专业】 | 基础数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-10-11 |
| 【中关键词】 | （输入存贮线性）有限自动机,积,弱可逆,极小,覆盖, |
| 【英关键词】 | （input-memory linear finite）automata,product,weak invertibility,minimum,covering, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>一般性问题>理论、方法>自动机理论 |
| 【论文摘要】 |
自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论。五十年代,在开关网络理论和数理逻辑中图灵机理论的基础上,形成了自动机理论这一数学分支学科。随着科学技术的发展,自动机理论有了深入的发展和广泛的应用,成为许多学科的重要理论和基础。
自动机理论中最重要的问题之一是技术实现问题,文献[1]给出了任意的线性有限自动机在一定条件下都可以等价嵌入于一个输入存贮线性有限自动机。也就是说,在一定条件下,任意的线性有限自动机的功能都可以通过输入存贮线性有限自动机来实现。文献[2]证明了任何延迟τ步可逆线性有限自动机都存在τ阶输入存贮线性有限自动机为它的延迟τ步逆。并且,输入存贮线性有限自动机在有限自动机公钥密码体制和数字签名中也有重要的应用[3-12]。而输入存贮线性有限自动机是一类典型的、易于实现的线性有限自动机。所以,我们有必要对输入存贮线性有限自动机进行讨论,以便进一步研究任意的线性有限自动机和为密码学、网络、自动控制、模式识别等而服务。
本文从输入存贮线性有限自动机本身出发对其进行研究,剖析了其自身结构,两个输入存贮线性有限自动机作积之后的结构,一个线性有限自动机M具有r阶输入存... |
| 【论文题纲】 |
|
中文摘要 |
3-8 |
|
英文摘要 |
8-15 |
|
第一章 引言 |
15-21 |
|
1.1 研究背景及我的研究成果 |
15-20 |
|
1.2 基本概念和记号 |
20-21 |
|
第二章 输入存贮线性有限自动机积的讨论 |
21-33 |
|
2.1 基本概念和记号 |
21 |
|
2.2 关于输入存贮线性有限自动机积的一些结果 |
21-33 |
|
第三章 输入存贮线性有限自动机的弱可逆性 |
33-40 |
|
3.1 基本概念和记号 |
33 |
|
3.2 延迟τ步弱可逆h阶输入存贮线性有限自动机的判别 |
33-36 |
|
3.3 延迟τ步弱可逆h阶输入存贮线性有限自动机的构造 |
36-37 |
|
3.4 延迟0 步弱可逆h阶输入存贮线性有限自动机的求弱逆 |
37-38 |
|
3.5 输入存贮线性有限自动机积的弱可逆性 |
38-40 |
|
第四章 输入存贮线性有限自动机的极小化 |
40-49 |
|
4.1 基本概念和记号 |
40 |
|
4.2 关于输入存贮线性有限自动机极小的判定和极小化的方法 |
40-49 |
|
第五章 状态机和变换半群积的覆盖关系 |
49-57 |
|
5.1 基本概念和记号 |
49-50 |
|
5.2 关于状态机和变换半群积的覆盖关系的一些结果 |
50-57 |
|
结束语 |
57-59 |
|
参考文献 |
59-62 |
|
读硕期间发表的论文目录 |
62-63 |
|
致谢 |
63-64 |
|
| 【DOI】 | LunWen.ID:2.2008.361864 |
