中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
有限自动机可逆性的若干结果
作者: 姚刚
答辩日期: 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|)。就目前计算机的能力而言,有限自动机加密体制是可以抵抗这个攻击算法的。
英文摘要: 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.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/7602
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW011276.pdf(1634KB)----限制开放-- 联系获取全文

Recommended Citation:
姚刚. 有限自动机可逆性的若干结果[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2003-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[姚刚]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[姚刚]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace