格值有限状态自动机的同态和商自动机

提出了格值有限状态自动机（LFSA）的同态、强同态的概念,研究了LFSAs同态、强同态的若干性质。在LFSAs强同态的基础上,得到了LFSA的商自动机及其最小化自动机,刻画了商自动机的性质。     

几类带空转移的n元伪加权自动机的关系

引入了n元伪加权有穷自动机——带有n个有限字符集的伪加权有穷自动机、分明型n元伪加权有穷自动机和确定型n元伪加权有穷自动机的概念。根据状态转移函数在每个字符集上是否带空转移, 将以上自动机分为4类:带r-型空转移的n元伪加权有穷自动机和带空转移的n元伪加权有穷自动机和带r-型空转移的分明型n元伪加权有穷自动机和带空转移的分明型n元伪加权有穷自动机。给出了以上自动机所识别语言的定义并探究了它们之间的关系,讨论了状态转移函数在每个字符集上是否带空转移对其接受语言的影响。     

基于等价关系的有穷自动机最小化方法

主要介绍了有穷自动机的基础知识,研究了有穷自动机的等价性,并在确定型有穷自动机的状态集上引入等价关系,给出了自动机的最小化过程。利用等价归并算法,可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉,生成与其等价的最小化的确定型有穷自动机。     

基于等价关系的有穷自动机最小化方法

主要介绍了有穷自动机的基础知识,研究了有穷自动机的等价性,并在确定型有穷自动机的状态集上引入等价关系,给出了自动机的最小化过程。利用等价归并算法,可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉．生成与其等价的最小化的确定型有穷自动机。     

扰动模糊有限转换状态机

引入了扰动模糊有限转换状态机和扰动模糊有限状态机的（强）同态的概念,研究了它们的相关性质。给出了[Σ]的元素构成所有长度有限的词集上的两种同余关系,讨论商结构问题,证明了相应的所有等价类构成具有单位元的有限半群,并且这两个有限半群是同态的。给出了[Q]上容许关系及强同态的核的概念,研究了它们的相关性质。     

赋权型自动机的不同模型研究

自动机理论是理论计算机科学的基础理论之一,在很多领域自动机有着广泛的应用,有穷状态自动机是正则语言的识别机器,通常分为确定型与非确定型两种模型,其识别语言的能力是等价的。赋权自动机是另一类重要的自动机模型,自动机的每条转移规则和状态可以赋以某一代数结构上的某一数值,从而可以计算输入字符串的权值。任何有穷状态自动机都可以视为一特殊赋权自动机,因此赋权自动机功能更强大,应用更为广泛。     

带空移动的加权有限自动机量化等价及其转换

在经典的有限自动机理论中,带空移动的有限自动机与不带空移动的有限自动机是等价的。取值于实数的加权有限自动机是自动机的一种推广模型,它给经典自动机的每个转换赋一个取值于实数的权值,这些权值表示执行转换的代价。为了研究带空移动的加权有限自动机与不带空移动的加权有限自动机是否具有等价性这一问题,提出量化等价的概念,并研究如何将一个带空移动的加权有限自动机转换为一个与之量化等价的不带空移动的加权有限自动机。研究结果表明:这两者是量化等价的。     

基于紧凑型有穷自动机模型的告警相关处理

在网络管理领域,告警相关（Alarm Correlation)是取代简单告警过滤机构的一种全新故障管理策略。通过在非确定型有穷自动机在(ndfa)的定义中引入状态基(State Cardinality)的概念,本文首先给出紧凑型有穷自动机（cfa）的定义,然后提出了基于紧凑型有穷自动机的告警相关处理模型并进行了详尽的描述。在一个电信管理网（TMN）的故障管理子系统中应用该模型对大量的告警信息在时间上和空间上进行告警相关处理。仿真结果表明,基于紧凑型有穷自动机的告警相关处理模型的算法实现具备简单、高效、实用和实时的特点,尤其对并发故障具有较强的相关处理能力。     

加权迁移系统线性时间属性及其安全性检测

针对加权迁移系统,提出了线性时间属性及其安全性检测。首先定义了半环K上的加权迁移系统,提出了加权线性时间属性概念,并根据权重函数确定加权线性时间属性的上确界、下确界和闭包; 接着给出了几种常见的加权线性时间属性并且讨论了它们的关系; 然后重点研究了加权安全性,通过加权自动机和闭包给出了加权正则安全性; 最后基于加权有穷自动机,建立了加权正则安全性的检测方法。检测过程结合半环和形式幂级数,构造了加权迁移系统和加权有穷自动机的乘积系统,将加权安全性检测问题转化为验证乘积系统的不变性,给出了加权正则安全性检测的算法和复杂度。实例结果表明,所提的方法能够对加权迁移系统的安全性进行检测。     

两类具有输出字符功能的模糊自动机的关系

在文中,对文献8中介绍的具有输出字符功能的模糊自动机和模糊有限状态自动机的定义作了修改,并对它们进行了系统的研究,揭示了此两类自动机和取分配格的代数性质的紧密联系;得到了此两类自动机在:(1)强等价;(2)等价;(3)弱等价条件下的许多重要结论。     

直觉模糊同步机与最小化

提出了具有输入和输出功能的直觉模糊同步机的概念,研究了直觉模糊同步机直觉容许关系、等价关系、同态的若干性质。在直觉模糊同步机同构的基础上,得到了极小化直觉模糊同步机。     

NON‐BLOCKING SUPERVISORY CONTROL FOR INITIALISED RECTANGULAR AUTOMATA

We consider the problem of supervisory control for a class of rectangular automata and more specifically for compact rectangular automata with uniform rectangular activity, i.e. initialised. The supervisory controller is state feedback and disables discrete‐event transitions in order to solve the non‐blocking forbidden state problem. The non‐blocking problem is defined under both strong and weak conditions. For the latter maximally permissive solutions that are computable on a finite quotient space characterised by language equivalence are derived.     

DISCRETE-TIME SYSTEMS THAT ADMIT FINITELY MANY CAUSAL STATE-REPRESENTATIONS

In this paper, relationship between causal discrete-time systems and the number of their causal state-representations is studied using the metric structure defined on the input and output sets of the systems, which enables us to introduce some topological notions to the investigation. For any given causal discrete-time system, an equivalence relation is defined on the input set, where any two inputs are equated if they equally distinguish all possible causal states of the system, and the quotient set of the input set with respect to the equivalence relation is studied in detail. The main results include: A discrete-time system admits essentially only a finite number of causal state-representations if and only if it is finitely observable. As an application, an algorithm to decide if a finite-state automaton has only finitely many automata having the same behavior as that of the original automaton is obtained.     

循环自动机的等价性

主要讨论了两个循环有限自动机的等价性与循环有限自动机的生成子之间的关系,在某些条件下给出了两个循环有限自动机等价的充分必要条件。     

概率有限自动机的积和分解

给出几种概率有限自动机的积,讨论了他们之间的相互关系,并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解,证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。     

Transformations of the one-dimensional cellular automata rule space

We introduce the notion of double permutation in order to study particular classes of transformations of the one-dimensional cellular automata rule space. These classes of transformations are characterized according to different sets of metrical, language theoretic, and dynamical properties they preserve. Each set of transformations we propose induces an equivalence relation over the cellular automata rule space. We give exact results on the cardinality of the quotient sets generated by these equivalence relations. Finally, we discuss some interesting open problems.     

一类并发实时系统的自动验证

一个被广泛用于验证实时系统的方法是根据被验证的实时性质,使用适当的双向模拟等价关系使无限的状态空间转化为有限的状态等价类空间.算法只需要在这个有限的等价类空间里搜索就可以得到正确答案.但是,这个等价类空间的规模一般随着系统规模的增大而产生爆炸性的增长,以至于在很多情况下,穷尽搜索这个空间是不现实的.该文引入了一个等价关系来验证一个由多个实时自动机通过共享变量组成的并发系统是否满足一个线性时段特性.同时,还引入了格局之间的兼容关系来避免对状态等价类空间的穷尽搜索.基于这两个关系,文章提出了一个算法来验证是否一个实时自动机网满足一个线性时段特性.实例研究显示,此算法在某些情况下比其他一些工具有更好的时间和空间效率.