输入可控的二元判定可编程控制器

二元判定自动机是借助于判定方法而不是用布尔逻辑来耱解开关函数的有限状态时序机，二元判定时序机（简称BDMs）在高速可编程控制器中的应用十分重要。因为BDMs的有效工作速度远远超过了普通微机处理器的有效工作速度。本文首次论了BDM求解时序函数的能力，以前研究者所定义的BDM表明，从自动机的理论上讲它的求解能力不如确定性有限状态自动机（简称DFA）的能力强，然而，用输入控制对BDM扩展之后表明其求解能力与DFA等效，这样BDM就可以用于完成有限状态时序函数的计算，本文旨在根据所期望的情况时空复杂性分析用BDM有限状态自动机取代较普通的自动机模型，同时阐述了由此分析所得出的硬件设计方法，并讨论编程方法。     

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

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

60/102/204混合细胞自动机的可逆性分析

细胞自动机的理论研究主要包括细胞自动机的分析和综合两个方面,而细胞自动机的可逆性分析则是细胞自动机分析中的核心问题。60/102/204混合细胞自动机作为一类重要的细胞自动机,利用矩阵分析方法将其状态转移表示为矩阵方程,从而分析其可逆性、可逆细胞自动机的数目和可逆细胞自动机的构造。60/102/204混合细胞自动机可逆性分析对于其在密码学、通信和测试等领域的应用具有重要意义。     

基于自动机模型的平面调车软件设计方法

 平面调车是一种铁路调车过程中的离散事件系统.可靠性高、易测试的平面调车软件对保障铁路运输安全极为重要,因此需要建立一种规范模型基础上的平面调车软件设计方法.分析了平面调车系统中事件驱动过程的复杂性以及自然语言规则描述方式的缺陷,提出通过自动机模型描述平面调车系统,具体讨论了平面调车系统与时间自动机(TA)、下推自动机(PDA)和分层自动机的关系.从状态划分、数据结构设计、状态转移流程等方面说明了基于自动机模型的平面调车软件的设计方法.     

基于有限状态机的UART设计

文章结合UART的设计，分析阐述了硬件设计中的有限状态自动机理论；并在分析UART功能特点的基础上，给出了利用有限状态自动机理论进行UART设计的实例，与其他设计方法相比较，利用有限状态自动机理论设计控制逻辑具有直观简单，设计流程短等优点，在EDA技术中必将发挥重要的作用。     

RRM终端一致性测试中置信度的判定和实现

从概率统计学的角度介绍了置信度的基本概念,说明了置信度对实际RRM终端一致性测试的具体要求,并分析了RRM测试中对于置信度判定理论依据、具体方法和实现手段。     

有限自动机的电气实现方法

自动机可用多种方法去实现,如用机械、液压、射流等方法,也可用计算机程序来实现。本文仅介绍用电路来实现自动机的方法。当机器处于状态S_i时,接受信息x_(ij)则转换为新状态S_j,在状态图中记作S_i x_(ij)→S_j若用触发器的组合来表达其状态,则可用触发器与逻辑器件组成实现自动机的电路。     

安全信息流的实时监控机制

提出了一种基于安全自动机的信息流实时监控技术,该技术防范了恶意用户通过程序结构的缺陷窃取机密信息.监控机制使用了下推自动机,结合动态分析技术和静态分析技术,利用清除函数的原理,通过状态变换实时检测信息流的安全性.在程序执行期间,对程序事件进行抽象并跟踪信息流,用安全自动机产生的断言控制目标程序的执行,防止非法操作.用C语言实现了安全自动机,实验结果证明这种技术是灵活实用的.     

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

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

精确学习模型下确定的有穷自动机的学习

利用多态自动机和有穷自动机的关系，根据多态自动机的学习算法，给出了EXACT学习模型下，确定的有穷自动机的学习算法，并对算法复杂度做了分析，说明确定的有穷自动机在EXACT模型下可以在多项式时间内进行学习。这样就可以用软件来模拟确定的有穷自动机的学习。     

Defining and Providing Coverage for Assertion-Based Dynamic Verification

With the emerging predominance of assertion-based dynamic verification, test generation is a key area where assertions can play a bigger role. Generation of test sequences from properties defined by assertions can help in finding failures in corner-cases of the design specification that without assertions may not be possible. As such, we rely on the duality between property checkers and test generators to take advantage of the information present in the assertions for effective test scenarios—a much needed endeavor given the increasing challenges in verification. To undertake such an effort, we first elaborate on the relation between the coverage of the assertion-based specification and the specific coverage metrics over finite nondeterministic automata representing the assertions. We finally present Airwolf-TG that generate test sequences from compact automata produced by the MBAC tool.     

基于元胞自动机的多重零水印算法

利用混沌序列随机选择图像元胞自动机变换的低频系数产生初始构型,元胞自动机根据初始构型演化出零水印,然后用其加载有意义的二值水印,从而实现多重水印的零嵌入,从根本上保证了水印的不可见性.由于算法是基于元胞自动机域的,充分利用了元胞自动机复杂多变的特性,使水印有很好的安全性.实验结果表明提出的算法有较好的鲁棒性,也很好地解决了常见零水印方案所面临的问题.     

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

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

量子元胞自动机全加器的布尔差分测试法

根据布尔差分测试法的基本原理以及量子元胞自动机(QCA)的缺陷特性,提出一种适用于QCA的测试方法。以QCA 1位全加器为例,采用QCA Designer软件,验证该方法的有效性与可行性,并与Tahoori等人提出的QCA电路测试法进行比较。结果表明,新设计的布尔差分测试法具有高故障覆盖率和易测性等优点,对未来复杂QCA电路的测试有一定的借鉴作用。     

A Test Generation Framework for Quantum Cellular Automata Circuits

In this paper, we present a test generation framework for quantum cellular automata (QCA) circuits. QCA is a nanotechnology that has attracted recent significant attention and shows promise as a viable future technology. This work is motivated by the fact that the stuck-at fault test set of a circuit is not guaranteed to detect all defects that can occur in its QCA implementation. We show how to generate additional test vectors to supplement the stuck-at fault test set to guarantee that all simulated defects in the QCA gates get detected. Since nanotechnologies will be dominated by interconnects, we also target bridging faults on QCA interconnects. The efficacy of our framework is established through its application to QCA implementations of MCNC and ISCAS'85 benchmarks that use majority gates as primitives     

用于光刻胶刻蚀过程模拟的二维动态CA模型

针对光刻工艺模拟,首次建立了光刻胶刻蚀过程模拟的2-D动态元胞自动机(CA)模型,通过制定规则来确定模拟过程中不断更新的表面元胞,使得模拟只需要计算表面元胞的刻蚀过程.模型既有稳定性好的优点,又有运算速度快的优点.采用一些公认的光刻速率分布测试函数非常有效地模拟了光刻过程,模型在刻蚀速率变化非常大的区域也非常稳定.     

网络协议中的时间约束测试

对协议实现的时间约束进行测试,是验证协议实现的实时特性的重要方法.本文考查了当前实时系统测试方面的进展,结合路由协议测试的实践,修正了现有方法几个不符合实际情况的假设,扩展了时间自动机的理论和思路,将时间约束下的状态机转换成非确定性有限状态自动机,运用Wp方法生成抽象测试集,讨论将抽象测试集参数化的方法.以路由协议RIP的时间约束为例说明了生成基于TTCN测试例的过程.     

Adaptive integrated image segmentation and object recognition

The paper presents a general approach to image segmentation and object recognition that can adapt the image segmentation algorithm parameters to the changing environmental conditions. Segmentation parameters are represented by a team of generalized stochastic learning automata and learned using connectionist reinforcement learning techniques. The edge-border coincidence measure is first used as reinforcement for segmentation evaluation to reduce computational expenses associated with model matching during the early stage of adaptation. This measure alone, however, cannot reliably predict the outcome of object recognition. Therefore, it is used in conjunction with model matching where the matching confidence is used as a reinforcement signal to provide optimal segmentation evaluation in a closed-loop object recognition system. The adaptation alternates between global and local segmentation processes in order to achieve optimal recognition performance. Results are presented for both indoor and outdoor color images where the performance improvement over time is shown for both image segmentation and object recognition