确定的与非确定的公式时钟自动机的等价性

本文分析了传统的时间自动机在实时系统进行形式化验证方面所存在的问题,提出了一种新的形式化验证工具——公式时钟自动机,给出了公式时钟自动机的形式化定义。在公式时钟自动机中,每一个事件对应一个命题、并且针对给定命题集上的每个时态公式,我们定义两个时钟:公式记录时钟与公式预测时钟。前者记录公式最近一次被满足时距目前的时间,后者预测下一次公式将被满足时距目前的时间。最后讨论了公式时钟自动机的确定性和非确定性,并证明了确定的公式时钟自动机和非确定的公式时钟自动机的等价性。     

一种改进的实时系统可达性分析算法

首先简介了时间自动机、时钟区域、区域等价、时钟带的概念.利用时钟带,可以将时间自动机的无穷状态空间转化为有穷.实时系统的绝大多数安全性和部分活性可以通过可达性分析算法来验证.然而,当系统时钟个数较多时,用DBM存储时钟带,会造成内存空间的很大耗费.该文提出了用邻接表存储时钟带,给出了改进的算法,并对算法的空间复杂度作了分析.实验表明,当时钟个数大于5时能节约很大的内存空间,从而在一定程度上缓解了状态爆炸.     

一种时间自动机时钟离散化算法

稠密时间自动机被广泛应用于实时系统自动验证.然而其在补操作下不封闭,因而导致多种线性实时性质不可验证.离散时间自动机虽不存在此问题,但该模型表达能力偏弱.因此,提出了一种时间自动机时钟离散化算法,结合时钟物理约束因素,证明了新方法可有效解决上述问题.     

Fuzzy有限自动机语言的运算封闭性

作者已对Fuzzy3型文法与Fuzzy有限态自动机的关系作了详细的研究,本文将在此基础上对Fuzzy有限自动机语言的性质作进一步讨论.证明了Fuzzy有限自动机语言对并、连接(乘积)及闭包运算具有封闭性.     

基于网表的量子元胞自动机时钟布局方案

量子细胞自动机(quantum cellular automaton,QCA)器件是一种具有时控工作特征的新型器件结构,与传统的通过电信号来表示二进制信息的方法不同,它是通过电子在QCA细胞上占据的位置来表示的。正是由于QCA器件的时控工作特征,若没有一个系统合理的方法设计QCA时钟电路,则会导致电路时钟设计复杂、电路时钟周期冗余。文章基于传统集成电路成熟的网表技术,引入了新的网表参数,使得在进行电路器件设计时也能解决时钟布局的设计,缩短了电路设计时间、提高了时钟的合理布局。     

广州地铁一号线时钟系统的应用

本文以广州地铁一号线时钟系统为列,探讨了地铁时钟系统的组成,功能和运行方式,并对地铁时钟系统发展作了展望。     

基于FPGA的元胞自动机模型

传统元胞自动机数学模型在计算机软件中的实现,受当前处理器顺序执行指令的特性和元胞自动机特殊的数据结构所限,无法同时实现高速度和高精度,因此将其移植到FPGA上实现.硬件实现的模型具有并行计算的特性,能够显著提高计算速度,芯片规模的快速扩大又为高精度的实现提供了可能.设计元胞自动机硬件模型,将其作为IP核嵌入SOPC系统中,在上位机控制下进行模型演化,并设计了软件模型进行参照.经测试,硬件模型能正确实现元胞机算法,在一个时钟周期内完成一代元胞演化,相比于软件模型显著提高了执行效率.     

基于QCA的三输入数值比较器设计

量子元胞自动机(quantum-dot cellular automata,QCA)是一种新兴的纳米器件。文章基于QCA提出了一位的三输入比较器设计方案,并用QCADesigner软件进行仿真。结果表明,所设计的电路具有正确的逻辑功能。在设计过程中采用共面交联和二维改进型时钟方案,有效提高数据的流水线性质及数据的并行计算优化度,此外,采用减少信息传输距离和分层的设计思想减少了整个电路的时钟延迟和横截面积。     

自动机和形式语言结构的理论研究

利用半群代数理论进一步讨论了自动机和形式语言的理论结构．首先构造了一个简单的有穷自动机的么半群，用代数理论分析了其性质，并推广到非确定性有穷自动机的情况．然后对字母表关于连接运算构成的么半群的性质作了进一步探讨，并给出了二进制串生成的半环，及研究了它的结构理论。     

最大乘积型Fuzzy文法与自动机

本文对最大乘积型Ｆｕｚｚｙ文法与乘积型Ｆｕｚｚ自动机的关系作了详细讨论得出两个重要的结论；由给定的最大乘积型Ｆｕｚｚｙ正规文法可构造出一个最大乘积型Ｆｕｚｚｙ自动机，使得它们接受的语文集相等，反之亦然。     

关于ω-有穷自动机的接受条件

关于ω－有穷自动要的接受条件的研究,旨在揭示ω自动识别语言的能力以及对语言类作进一步的划分,到目前为止ω－自动机的接受条件已有六种,本文给出了一些新形式的接受条件并且研究了ω－有穷自动机在这些接受条件下接受ω－语言的能力。     

非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

CFSM模型的有限自动机语义

研究CFSM模型的自动机语义,提出了一种从CFSM到自动机转换的算法。该算法的核心思想是构造一个包含控制自动机、输入自动机、输出自动机的有限状态自动机系统,利用自动机的同步性模拟CFSM的异步行为。本文的工作为进一步利用自动机理论和工具对CFSM模型进行分析和验证奠定了基础。     

地理元胞自动机研究综述

从地理元胞自动机的应用范围、地理元胞自动机转换规则的获取、地理元胞自动机空间划分、元胞自动机与GIS的集成等方面回顾了地理元胞自动机模型的研究,对地理元胞自动机模型研究的发展趋势进行了分析,认为地理元胞自动机模型研究在以下几个方面需要进一步深入：（1）应用范围应进一步扩大;（2）在确定地理元胞自动机的转换规则时应综合考虑自然因素和社会经济因素;（3）应加强地理元胞自动机与多智能体系统的集成研究;（4）应加强对地理元胞自动机的尺度划分及尺度效应的研究;（5）应进一步深化地理元胞自动机与GIS的集成研究。     

一类特殊形式的Fuzzy正则语言注记

对一类特殊形式的Fuzzy正则语言作了一定的讨论,得到了两个重要定理,为进一步研究Fuzzy正则语言与Fuzzy有限状态自动机的关系奠定了基础．     

有关本原自动机的研究

讨论了本原自动机的自同态,证明了如果广义正规自动机Α的所有本原自动机都是Sl(或G)-自动机,那么Α也是Sl(或G)-自动机;证明了强连通本原自动机的并是G-自动机;利用极小生成元集将标准自动机的定义推广到有限自动机,给出了广义标准自动机的定义及其成立的一个充分条件。     

基于DS1302和LM016L的实时时钟设计与仿真

本文给出了一个单片机控制的液晶显示实时时钟设计实例,系统地介绍了实时时钟芯片DS1302的主要工作原理和编程思路。对字符液晶显示器LM016L的显示原理和技巧作了阐述。系统在Proteus平台上进行了软、硬件交互仿真,实现了设计目的。     

时间校验仪

本文介绍了校验复费率和多功能电能表的时钟频率和时段误差的基本原理,并介绍了一种采用高精度石英晶体和GPS作基准频率和时钟,由大规模集成电路组成的时间校验仪。     

时间自动机与信号自动机的互模拟算法

基于时间自动机的验证工具已被广泛应用于实时系统模型验证。信号自动机为一类实时系统建立了比时间自动机更适合的模型,但是它还不能用于实际的实时系统模型验证,因为没有验证算法可用。把信号自动机验证问题归约到了时间自动机验证问题：证明了两种自动机具有相同的识别语言能力,证明了二者具有双向模拟关系,并在此基础上提出了线性的互模拟算法。把互模拟算法和已有的时间自动机验证算法结合起来,就得到了信号自动机的验证算法,从而解决了对信号自动机模型的验证问题。     

实时调度问题的形式化描述及分析

使用自动机理论建立了一个用于分析实时调度问题的、可化简归并的形式化方法。通过分析单个任务的状态变化过程来构造实时系统的自动机。对自动机的状态进行化简和归并,大大降低了讨论实时调度问题的复杂度。以优先级上限协议为例构造了确定有穷自动机并使用该自动机证明了优先级上限协议的性质。