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

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

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

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

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

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

基于层次时间自动机的动态行为取证建模方法

提出一种新的动态行为取证层次化模型.首先介绍层次时间自动机的概念,接着详细阐述动态行为的层次时间自动机形式化模型及其组合模型,然后分析组合模型中可能存在的非法行为.     

时间自动机流量特性的硬件模拟

在实时网络中,受到突发度等指标约束的流量特性是最坏情况下服务质量保证的关键因素之一。采用时间自动机对流量进行模拟,可以反映在到达曲线的组合约束下流量的不确定性。采用硬件描述语言对相应的时间自动机形式化模型进行转换,研究了硬件逻辑与时间自动机模型的对应方法,利用可编程阵列芯片并发运行的优势,充分体现了时间自动机之间的并发行为,用于进行硬件在回路测试。采用此方法构成流量特性模型的转换接口,并采用硬件描述语言实现,经过在典型测试用例下的仿真测试,发现该装置能够根据模型参数对于虚拟链路的流量特性进行约束,模拟生成综合化网络中的实时通信流量,说明了该硬件模拟方法的可行性。     

一种价格时间Petri网的状态空间计算

价格时间Petri网是对web服务过程和工作流模型等进行时间和成本分析的一种新工具.而价格时间自动机则是一种相对成熟的工具.提出一种状态空间计算方法,可以将价格时间Petri网的状态空间构造为一个价格时间自动机.该方法的核心思想是在扩展状态类中增加价格参数.进一步证明了构造出的价格时间自动机和初始的价格时间Petri网是双相似的.     

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

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

状态差计数法及其置信度的估计

本文提出了一种新的压缩电路输出信息的方法－状态差计数法，估计了该法的测试置信度，分析了置信度标准的一些性质，用有限状态自动机建立了测试过程的模型，用马尔科夫链描述了自动机状态间的相互转换，求出了测试置信度与测试序列长度间的相互关系，实验表明，分析数据与模拟结果是吻合的。     

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

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

可编程细胞自动机伪随机序列发生方法

可编程细胞自动机不仅具有细胞自动机组成单元的简单规则性、单元之间作用的局部性和信息处理的高度并行性等特性,而且具有动力学行为的复杂变化性.基于具有不可约特征多项式的规则90/150加性细胞自动机的同构特性,本文提出了可编程细胞自动机伪随机序列发生方法,其系统的结构参数随时间变化而变化,从而使得系统具有复杂的动力学行为.计算机模拟实验表明基于可编程细胞自动机的伪随机序列发生方法实现简单,产生的伪随机序列具有周期大、速度高和随机统计特性好等优点.     

基于元胞自动机的图像边缘检测新方法

具有自组织性并行行为的元胞自动机模型已逐步应用于图像处理领域。在已有的基于元胞自动机的图像处理算法基础上,结合元胞自动机和图像边缘的种种特征,提出了一种新的适用于图像边缘检测的元胞自动机模型。实验证明,新模型更加有效地勾勒出图像细节边缘。同时,该模型也适用于高分辨率遥感图像中小目标的边缘检测和提取。     

Minimization of Fuzzy Finite Generalized Automata

Some concepts in Fuzzy Generalized Automata （FGA） are established. Then an important new algorithm which would calculate the minimal FGA is given. The new algorithm is composed of two parts： the first is called E-reduction which contracts equivalent states, and the second is called RE-reduction which removes retrievable states. Finally an example is given to illuminate the algorithm of minimization.     

Specifying and proving properties of timed I/O automata using Tempo

Timed I/O automata (TIOA) is a mathematical framework for modeling and verification of distributed systems that involve discrete and continuous dynamics. TIOA can be used for example, to model a real-time software component controlling a physical process. The TIOA model is sufficiently general to subsume other models in use for timed systems. The Tempo Toolset, currently under development, is aimed at supporting system development based on TIOA specifications. The Tempo Toolset is an extension of the IOA toolkit, which provides a specification simulator, a code generator, and both model checking and theorem proving support for analyzing specifications. This paper focuses on the modeling of timed systems and their properties with TIOA and on the use of TAME4TIOA, the TAME (Timed Automata Modeling Environment) based theorem proving support provided in Tempo, for proving system properties, including timing properties. Several examples are provided by way of illustration.     

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

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

从线性时序逻辑公式到自动机的转换算法

To combat the well-known state-space explosion problem in Propositional Linear Temporal Logic (PLTL) model checking, a novel algorithm capable of translating PLTL formulas into Nondeterministic Automata (NA) in an efficient way is proposed. The algorithm firstly transforms PLTL formulas into their non-free forms, then it further translates the non-free formulas into their Normal Forms (NFs), next constructs Normal Form Graphs (NFGs) for NF formulas, and it finally transforms NFGs into the NA which accepts both finite words and infinite words. The experimental data show that the new algorithm reduces the average number of nodes of target NA for a benchmark formula set and selected formulas in the literature, respectively. These results indicate that the PLTL model checking technique employing the new algorithm generates a smaller state space in verification of concurrent systems.     

An efficient design of CORDIC in Quantum-dot cellular automata technology

Power dissipation of future-integrated systems, consisting of a numberless of devices, is a challenge that cannot be easily solved by classical technologies. Quantum-dot Cellular Automata (QCA) is a Field-Coupled Nanotechnology (FCN) and a potential alternative to traditional CMOS technologies. It offers various features like extremely low-power dissipation, very high operating frequency and nanoscale feature size. This study presents a novel design of CORDIC circuit based on QCA technology. The proposed circuit is based on several proposed QCA sub-modules as adder and Flip-Flop. To design and verify the proposed architecture, QCADesigner tool is employed and power consumption is estimated using QCAPro software. The proposed QCA CORDIC achieves about 69% reduction in power and area compared to previous existing designs. The outcome of this work can open up a new window of opportunity for the design of the CORDIC module and can be used in low-power signal and image processing systems.     

基于QCA的五输入Majority门设计及应用

Majority门作为多数逻辑电路的基本逻辑单元,其性能直接影响整体电路的质量.使用量子元胞自动机（QCA）设计Majority门具有结构简单的优点.本文提出了一种三层电路实现五输入Majority门的设计,并以此设计了全加器,进一步应用于多位加法器和乘法器中,与已发表的电路设计比较表明,其版图使用面积和元胞数有明显的减少,加法器元胞数和面积改进最高可达43%和87.2%,乘法器元胞数和面积改进最高可达48.2%和100%.     

A new reconfigurable Test Vector Generator for built-in self-test applications

This paper proposes a new approach to designing a BIST Test Vector Generator (TVG) for random vector-resistant circuits based on reconfigurable Cellular Automata Registers (CARs). Each CAR configuration is constructed by combining rules 90 and 150 and the same approach can also be applied to the Linear Feedback Shift Register (LFSR). The TVG thus designed is able to produce 100% fault coverage with short test time at the cost of low area overhead. To achieve this objective, a new method called the Rank Order Clustering (ROC) method, is introduced in order to fix a number of inputs at certain values when generating pseudorandom vectors. It is shown that the ROC method is very simple and efficient in fixing inputs at these values in terms of complexity. Experimental results have been conducted to demonstrate the applicability of the proposed approach in terms of hardware size and test application time.     

Design and simulation of sequential circuits in quantum-dot cellular automata: Falling edge-triggered flip-flop and counter study

Quantum-dot Cellular Automata (QCA) is an emerging nanotechnology, with extremely small feature size and ultralow power consumption comparing with transistor-based technology. Anteriority, basic level-triggered flip-flop designs based on QCA implementation were examined. In this paper, we utilize the unique QCA characteristics and clock zones to design falling edge-triggered J-K flip-flop that is stable and practical. Simulation with the QCADesigner simulator is performed to verify the functionality of the proposed falling edge-triggered flip-flop. This paper also explores the design of counters. Synchronous counters are designed with several different bit sizes and simulation results demonstrate the validity of them.     

Novel RAM cell designs based on inherent capabilities of quantum-dot cellular automata

Quantum Cellular Automata (QCA) is a novel and attractive method which enables designing and implementing high-performance and low-power consumption digital circuits at nano-scale. Since memory is one of the most applicable basic units in digital circuits, having a fast and optimized QCA-based memory cell is remarkable. Although there are some QCA structures for a memory cell in the literature, however, QCA characteristics may be used in designing a more optimized memory cell than blindly modeling CMOS logics in QCA. In this paper, two improved structures have been proposed for a loop-based Random Access Memory (RAM) cell. In the proposed methods, the inherent capabilities of QCA, such as the programmability of majority gate and the clocking mechanism have been considered. The first proposed method enjoys smaller number of cells and the wasted area has been reduced compared to traditional loop-based RAM cell. For the second proposed method, the memory access time has been duplicated in presence of smaller number of cells. Irregular placement of QCA cells in a QCA layout makes its realization troublesome. So, we have proposed alternative versions of the proposed methods that exploit regularity of clock zones in design and have compared them to each other. QCA designer has been employed for simulation of the proposed designs and proving their validity.