| 有限自动机可逆性的若干结果 |
| 其他题名 | Some Results of Finite Automata Invertibility
|
| 姚刚
|
| 专业 | 计算机软件与理论
|
| 2003
|
| 学位授予单位 | 中国科学院软件研究所
|
| 学位 | 博士
|
| 学位授予地点 | 中国科学院软件研究所
|
| 关键词 | 有限自动机
矩阵环
延迟
（弱）可逆
半输入存贮
前馈可逆
合成
分解
|
| 摘要 | 自动机理论主要研究离散数字系统的功能、结构及其关系。随着微电子技术和信息科学的发展，自动机理论向信息技术的各个应用领域渗透，为它们提供理论模型、设计技术和运行算法。有限自动机可逆性理论是自动机理论的一个研究方向。对自动机可逆性的研究是从提出信息无损失和有限阶信息无损失的概念开始的，有限自动机公钥密码体制的提出与应用，促进了自动机可逆性理论的发展。本文给出有限自动机可逆性理论的几个研究结果。本论文的主要工作包括三个部分：矩阵环上有限自动机的可逆性理论，前馈逆有限自动机和弱可逆有限自动机的结构以及弱可逆有限自动机的分解问题。在第一部分中，我们研究了矩阵环上有限自动机的可逆性理论。矩阵环是一类典型的非交换环，并且具有较好的代数结构和丰富的研究结果。我们得到这样的结论：设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|）。就目前计算机的能力而言，有限自动机加密体制是可以抵抗这个攻击算法的。 |
| 其他摘要 | The main domains of automata theory include the function, structure and relation of the discrete digital system. With the development of electronic technology and the information theory, automata theory goes into every area of information technology, and provides theoretical models, design technology and algorithm to them. The invertibility of finite automata is one of the areas in automata theory and it has been studied since the concepts of the information lossless and the information lossless of finite order were proposed. The proposition and application of the finite automata public key cryptosystem stimulates the investigation of invertibility of finite automata. In this thesis, several results are given in the areas of the invertibility of finite automata. The main work of this thesis contains three parts: the invertibility of finite automata on matrix ring, the structure of feedforward inverse finite automata and weakly invertible finite automata, and the decomposition of weakly invertible finite automata. In the first part, we study the invertibility of finite automata over a matrix ring. Matrix ring is a typical noncommutative ring and it has fine structure and lots of achievement. We get the following result: Let M be a QL-type finite automaton over a matrix ring and M the corresponding linear finite automaton of M over the basic field, then M is weakly invertible with delay r if and only if M is weakly invertible with delay r. Therefore, the invertibility of finite automata over a matrix ring is transformed into the invertibility of finite automata over a field. Then, we give some results of the invertibility of finite automata over a matrix ring. In the second part, we study the structure of feedforward inverse finite automata in general case, and we also discuss the structure of weakly invertible finite automata, A form of structure of feedforward inverse finite automata with delay r is given in the situatkm that C(M_a,f) is a c-order semi-input-memory finite automata where autonomous finite automaton Ma＝（Y_a，S_a，δ_a，λ_a） is cyclic and the number of input alphabet set is equal to the number of output alphabet set. We also discuss a form of structure of feedforward inverse finite automata with delay r in the situation that the number of input alphabet set is different to the number of output alphabet set. At last, we give a form of structure of weakly invertible finite automata with delay r, and an algorithm to construct the n-ary weakly invertible finite automata with delay 2. In the third part, we study the decomposition of weakly invertible finite automata. First, we present an algorithm to decompose a kind of weakly invertible finite automata with delay 2 satisfied the special condition. Then we extend this algorithm so that we can decompose a kind of weakly invertible finite automata with delay r satisfied the special condition. Next, we give an algorithm to attack the finite automata public key cryptosystem. At last, we analyse the time complexity of the algorithm. The time complexity of this attack algorithm is O（p~（mτ-m-r_1-r_2-…-r_(τ-2)|S|）. So, the finite automata public key cryptosystem can resist this attack under the computation power of the computer now. |
| 页数 | 108
|
| 语种 | 中文
|
| 内容类型 | 学位论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/7602
|
| 专题 | 中科院软件所_中科院软件所
|
推荐引用方式
GB/T 7714 |
姚刚. 有限自动机可逆性的若干结果[D]. 中国科学院软件研究所. 中国科学院软件研究所,2003.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论