有限自动机可逆性的若干结果
文献类型：学位论文
| 作者 | 姚刚 |
| 学位类别 | 博士 |
| 答辩日期 | 2003 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 中国科学院软件研究所 |
| 关键词 | 有限自动机 矩阵环 延迟 （弱）可逆 半输入存贮 前馈可逆 合成 分解 |
| 其他题名 | Some Results of Finite Automata Invertibility |
| 学位专业 | 计算机软件与理论 |
| 中文摘要 | 自动机理论主要研究离散数字系统的功能、结构及其关系。随着微电子技术和信息科学的发展，自动机理论向信息技术的各个应用领域渗透，为它们提供理论模型、设计技术和运行算法。有限自动机可逆性理论是自动机理论的一个研究方向。对自动机可逆性的研究是从提出信息无损失和有限阶信息无损失的概念开始的，有限自动机公钥密码体制的提出与应用，促进了自动机可逆性理论的发展。本文给出有限自动机可逆性理论的几个研究结果。本论文的主要工作包括三个部分：矩阵环上有限自动机的可逆性理论，前馈逆有限自动机和弱可逆有限自动机的结构以及弱可逆有限自动机的分解问题。在第一部分中，我们研究了矩阵环上有限自动机的可逆性理论。矩阵环是一类典型的非交换环，并且具有较好的代数结构和丰富的研究结果。我们得到这样的结论：设M是矩阵环上的QL一型有限自动机，万为基域上M对应的线性有限自动机，则M延迟丁步弱可逆的充分必要条件是丽延迟τ步弱可逆。因此，我们可以将矩阵环上有限自动机的可逆性理论转化到有限域上进行研究，这样，我们给出了矩阵环上有限自动机的可逆性理论的一些结果。在第二部分中，我们研究了较一般情形下前馈逆有限自动机的结构，并且讨论了弱可逆有限自动机的结构。对一个c阶半输入存贮有限自动机C（M_a，f），自治有限自动机Ma＝（Y_a，S_a，δ_a，λ_a）的状态为一回路，并且输入字符集与输出字符集的数目相同的清况下，给出了延迟丁步前馈逆结构的一种刻划。我们还在输入字符集与输出字符集的数目不同的情况下，对前馈逆的结构作了初步的探讨。我们给出了弱可逆有限自动机的结构的一种刻划，并且给出了n元延迟2步弱可逆有限自动机的一个构造算法。在第三部分中，我们研究了弱可逆有限自动机的分解问题。我们先对于一类满足指定条件的延迟2步弱可逆有限自动机给出了一个分解算法，然后我们推广了这个算法，使它可以分解一类满足指定条件的延迟：步弱可逆有限自动机，并由此给出有限自动机加密体制的一个攻击算法。在给出攻击算法之后，我们分析了算法的时间复杂度，其复杂度为O（p~（mτ-m-r_1-r_2-…-r_(τ-2)|S|）。就目前计算机的能力而言，有限自动机加密体制是可以抵抗这个攻击算法的。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 108 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/7602]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 姚刚. 有限自动机可逆性的若干结果[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2003. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。