基于DNA有穷自动机的素性测试法

有穷自动机,一种计算能力极其有限的计算模型,具有解决素性测试的能力通过构造法得到了证明。既而提出了一种基于有穷自动机的测试一个整数是否为素数的DNA算法,并且详细描述了该有穷自动机的构造方法,将有穷自动机的状态用DNA单链分子来编码,而输入则用DNA双链分子编码,用带环的双链DNA分子来编码状态转移规则,通过限制性内切酶的切割实现状态的转移。该算法的创新之处在于它是基于有穷自动机这种计算能力极其有限的计算模型的,并且该算法不仅能判断一个整数是否是素数,还能用于素因子分解。该算法的优点是实验实现容易,所需的时间是输入的多项式函数而不是指数函数。     

基于确定有穷自动机描述的仿人智能控制记忆

模仿熟练操作者通过记忆多步连续调控系统的方式,将记忆用上下文无关文法表示.根据控制经验和滚动预测优化建立特征状态转换表和构造不确定有穷自动机,给出了转换确定有穷自动机的算法.在任意特征状态下,通过一系列的DFA状态转换函数的复合运算,得到使系统稳定下来的控制模态序列.     

一种基于确定型有穷自动机的动物识别系统的设计方法

提出了一种新的动物识别系统的设计方法.通过对有穷自动机理论与动物识别系统进行分析,建立了一个基于动物特征的确定型有穷自动机的模型.该模型描述了当输入一个动物特征值后,自动机的状态将发生转移,当输入的动物特征值充足时,即可识别出动物的种类.最后,根据这种模型设计出了动物识别系统,并上机进行了实现.     

动态异构冗余结构的拟态防御自动机模型

动态异构冗余结构是拟态防御技术的常用工程模型.然而,目前尚缺乏对该结构实施形式化分析的手段,因为该结构缺乏形式化建模方法.针对此问题,使用有穷状态自动机及其并行组合自动机为一些拟态攻防行为建立计算模型.首先,使用单个有穷状态自动机为单个执行体建模;其次,使用有穷状态自动机的并行组合为执行体组合建模;再次,修改状态迁移规则,得到可描述攻防行为的拟态防御自动机模型;最后,根据该自动机模型的状态条件,分析动态异构冗余结构上拟态攻防行为的安全性.此外,也可使用交替自动机为拟态攻防建模,并把安全性自动分析规约为交替自动机模型检测问题.     

基于PFADS的网络数据获取平台的研究与实现

随着IPv6网络的发展,基于IPv6的网络管理系统亟待开发。针对IPv6与IPv4长期共存的情况,论文提出一个基于并行有穷状态自动机的、双协议栈PFADS的网络信息获取平台。该平台采用有穷状态自动机进行协议还原,同时采用双直达式缓冲区和并行自动机方法,能满足在大规模网络下的信息获取,保证数据获取的实时性与准确性。     

基于规则模板的正则表达式分组算法

采用规则分组的方法解决确定型有限自动机(Deterministic Finite Automata,DFA)状态爆炸问题,随着分组数目的增加,匹配效率大大降低.本文提出正则表达式的输入驱动特性理论,并基于此提出了基于规则模板的分组算法——模板有限自动机.模板有限自动机算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎.理论分析和实验表明,与典型的DFA改进算法相比,预处理时间和存储空间有2～3个数量级别的缩减,且匹配效率没有明显降低.     

时间自动机两种模型的构造互模拟研究

基于时间自动机不同模型的验证被工业界广泛应用，本文形式描述了两种这样的模型，给出了从事件时钟自动机到双向时间自动机的构造方法，证明了二者识别语言之间的包含关系。     

基于启发式SCCs的广义Büchi 自动机判空检测算法

 基于自动机理论模型检测的一个关键算法是判断有穷状态系统是否满足属性的判空检测.对标准Büchi自动机作判空检测,容易引起状态爆炸.本文以TGBA为研究对象,提出基于启发式SCCs的广义Büchi自动机判空检测算法.该算法在on-the-fly算法的基础上结合启发式深度优先搜索和SCCs检测算法,能较快地判断TGBA的非空性.通过正确性证明、复杂性分析和实验验证了该算法的正确可行性.在TGBA非空的情况下,该算法的时空性能比已有算法更优.     

基于有限状态自动机的复合事件监测模型

通过对复合事件的自动机检测模型的研究，给出了构造事件表达式的自动机模型的完整过程。其中的关键步骤：从复合事件到NFA，从NFA到DFA都进行了详细的说明。在NFA向DFA转换过程中给出了子集构造算法、状态最小化算法。     

以DNA为载体的线性时序逻辑模型检测

线性时序逻辑模型检测被广泛应用于处理器设计与验证、网络协议验证、安全协议验证等领域.然而到目前为止,该技术只能在电子计算的平台上实现.为了以脱氧核糖核酸(Deoxyribo Nucleic Acid,DNA)为载体对线性时序逻辑(Linear Temporal Logic,LTL)实施模型检测,给出了使用粘贴自动机实现Until算子模型检测的方法.首先,使用粘贴自动机对Until公式的有穷状态自动机(Finite State Automata,FSA)模型进行编码;然后,将系统模型转换为粘贴自动机的输入字符串;最后,用粘贴自动机验证系统是否满足公式.仿真实验结果证实,新方法可实现对LTL逻辑时序算子的检测.     

Learning automata routeing in connection-oriented networks

Learning automata are used at the source nodes of a connection-oriented network to dynamically route newly arriving virtual calls to their destination. First, two new learning automata are introduced. Then, these two learning automata, as well as the well-known L Learning automaton and the deterministic shortest-path algorithms are used in a simulation program to route virtual calls. The more frequent the updating and the more recent network state information used, the better the performance. In the sequence, the virtual link length is developed as a function of both the number of packets and the number of virtual calls at the network link. This virtual link length is used in the learning automata routeing algorithm and is shown via simulation to be superior to the minimum packet delay or shortest-queue-type link length, usually used in real networks. Thus, in connection-oriented networks, not only the packet but also the virtual call traffic characteristics should be used in the routeing decisions. Furthermore, when the network state information is out-of-date, or when there are few virtual calls and each one carries a large number of packets, then the virtual link length should be based more on the number of virtual calls than on the number of packets at this link. On the other hand, when the network state information is current and there are many virtual calls and each one carries a small number of packets, then the virtual link length should be based more on the number of packets than on the number of virtual calls at this link.     

基于状态约束的大规模正则表达式匹配算法

通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程,分析内存增长的原因,提出了一种基于状态间约束关系的正则表达式匹配算法Group2-DFA。Group2-DFA通过两级分组,利用状态间的约束关系,将原始NFA转化为NFA和DFA的混合结构。实验表明,在保持一定处理速率的前提下,Group2-DFA能够有效地减少内存占用。在300条规则下,Group2-DFA吞吐率能够达到1Gbps,并且减少约75%的状态数。     

A Learning Automata Based Area Coverage Algorithm for Wireless Sensor Networks

One way to reduce energy consumption in wireless sensor networks is to reduce the number of active nodes in the network. When sensors are redundantly deployed, a subset of sensors should be selected to actively monitor the field （referred to as a ＂cover＂）, whereas the rest of the sensors should be put to sleep to conserve their batteries. In this paper, a learning automata based algorithm for energy-efficient monitoring in wireless sensor networks （EEMLA） is proposed. Each node in EEMLA algorithm is equipped with a learning automaton which decides for the node to be active or not at any time during the operation of the network. Using feedback received from neighboring nodes, each node gradually learns its proper state during the operation of the network. Experimental results have shown that the proposed monitoring algorithm in comparison to other existing methods such as Tian and LUC can better prolong the network lifetime.     

基于自动机理论的自动循迹搜索目标算法

自动机是一种抽象的计算模型,它可以根据输入的字符串来实现状态与状态之间的跳转。基于这个特点,可以把自动机理论运用搜索目标问题当中。以贪吃蛇自动寻找食物为例,利用确定型有空自动机理论,把贪吃蛇搜索到网格进行标记并设置成相应的状态。以实现贪吃蛇绕开障碍物并且不触碰其蛇身,在游戏景中自动规划出一条最短路径到达目标食物的位置。     

Learning automata–based multilevel medium access control in cyber physical system–based smart wireless networks

The performance of cyber physical system–based smart wireless networks depends on effective channel access by reducing the blocking, the dropping probability, and collisions. The aim of this proposed algorithm is to reduce the collisions in cyber physical system–based smart wireless networks. In this paper, multilevel medium access control in cyber physical system–based smart wireless networks is proposed. The optimal number of levels of gateways is determined using the concept of learning automata. Priority and time limit are assigned to every packet that is being transmitted. The proposed algorithm is evaluated and compared with two‐level medium access control in cyber physical system–based smart wireless networks, which is referred as priority with counter modified backoff (PCMB). The parameters used for evaluating the performance are throughput, delay, % of collisions, and number of packets dropped. The results project that the proposed algorithm accomplishes improved performance than PCMB.     

改进的安全协议自适应分析算法

提出一种改进的安全协议自适应分析算法,即修正学习算法La*,解决部分教师缺乏经验的问题,并将字符集扩展为大字符集。对提出的修正学习算法,进行了正确性证明和复杂度分析。该修正学习算法将有助于提高安全协议自适应模型检测的效率、降低分析和设计成本、缓解状态空间爆炸并增强协议本身对环境和各种攻击手段的防御能力。     

新颖的正则NFA引擎构造方法

提出了一种新颖的正则NFA引擎构造方法——PFA构造法。PFA构造法包括3个主要算法：预处理算法、解析树编码算法和基于编码树的NFA构造算法。采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp。NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小。     

Learning automata-based receiver conflict avoidance algorithms forWDM broadcast-and-select star networks

The increasing bandwidth demands of the emerging new generation of computer communication networks have led to the utilization of optical fiber as a transmission medium. A new receiver conflict avoidance algorithm for wavelength-division multiplexing (WDM) broadcast-and-select star networks is introduced. The proposed algorithm is based on the use of learning automata in order to reduce the number of receiver conflicts and, consequently, improve the performance of the network. According to the proposed scheme, each node of the network is provided with a learning automaton; the learning automaton decides which of the packets waiting for transmission will be transmitted at the beginning of the next time slot. The asymptotic behavior of the system, which consists of the automata and the network, is analyzed and it is proved that the probability of choosing each packet asymptotically tends to be proportional to the probability that no receiver conflict will appear at the destination node of this packet. Furthermore, extensive simulation results are presented, which indicate that significant performance improvement is achieved when the proposed algorithm is applied on the basic DT-WDMA protocol     

A Modified Oja–Xu MCA Learning Algorithm and Its Convergence Analysis

The original Oja-Xu minor component analysis (MCA) learning algorithm is not convergent. This brief shows that by modifying Oja-Xu MCA learning algorithm with a normalization step the modified one could be convergent subject to some conditions satisfied. The convergence of the modified MCA learning algorithm is studied by analyzing the convergence of an associated deterministic discrete time system. Necessary and sufficient conditions for convergence are obtained. Simulations further confirm the results