基于完备剩余格值逻辑的自动机和文法理论

初步建立基于完备剩余格值逻辑自动机与文法理论的基本框架。引入l值正则文法的概念,证明了任意l值自动机识别的语言等价于某种l值正则文法所生成的语言,反之,任意l值正则文法所生成的语言等价于某种l值自动机识别的语言。获得l值自动机及被l值自动机识别的语言的连接问题刻画。特别地,建立l值和L值泵引理,并得到l值语言的判定性刻画。最后,揭示带ε移动的l值自动机与不带ε移动的l值自动机之间的两个等价关系。     

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

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

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

结构化程序设计思想在形式语言与自动机理论中的体现

在形式语言与自动机理论课程中,文法与自动机的构造在本质上都与结构化程序设计的思想有着很强的联系。本文从具体例子出发,阐明了这种联系并将其上升到理论的高度。在教学实践中对这种联系的讲述,对学生理解和掌握文法和自动机的构造起到了非常积极的作用。     

形式语言与自动机理论课程教学方法探讨与实践

分析形式语言与自动机理论研讨式教学中侧重个性化教育的思想,提出在课堂教学中借助于思维导图、JFLAP等教学软件的方法,介绍教学实施过程,探讨相匹配的考核方法。     

基于自动机XML正则路径表达式查询研究

基于自动机正则路径表达式查询技术是半结构化数据模式下XML查询研究领域颇有价值的方法。许多研究方法对含有“//”操作符和“*”通配符复杂正则路径重写都会产生大量中间路径。设计了处理XML正则路径查询高效方法——CSAS,利用对象交换模型(OEM)作为XML数据模型,有限自动机作为查询模型,提出裁剪XMLSchema转化的自动机片断作为重写自动机来重写“//”和“*”符号的重写技术;利用剪枝技术、谓词处理后移策略实现查询优化。实验证明,CSAS方法是一种高效的XML正则路径表达式查询方法。     

基于Unsharp量子逻辑的自动机和文法理论

初步建立了具有某种分配律的扩展格序效应代数和格序QMV代数这两种unsharp量子结构上的自动机与文法理论的基本框架。引入了ε-值正则文法的概念,证明了任意ε-值自动机识别的语言等价于某种ε-值正则文法所生成的语言;反之,任意[ε]-值正则文法所生成的语言等价于某种ε-值自动机识别的语言。讨论了ε-值正则语言在和、连接及反转运算下的封闭性质。     

基于事件反馈的DES监控理论

本文首先综述了近年基于事件反馈的ＤＥＤＳ监控理论取得的进展，着重给出了几个主要研究方向的结果和存在的问题，同时对这一理论的应用领域特别是工业过程中的应用进行了讨论，指出了今后的发展方向。     

处理图像语言的格点自动机与格点文法

Giammarresi与Restivo在一篇综述中总结出一个关于可识别的图像语言(即2维矩形语言)REC的等价性定理.对比1维字语言的相应结果,其中还缺少关于生成文法的相应一环.提出了一种(矩形的)格点文法,正好弥补了这一缺环.而取代2维on-line tesselation自动机,引入了格点自动机的概念.一方面,它与经典的2元树型自动机更相似,另一方面,它也是格点文法与等价性定理中关于REC的其他描述方式之间的一座桥梁.同时,标准的existential monadic二阶逻辑也被一种更弱的规范框架——positive monadic分划逻辑所取代.由此导出一个新的更完整的关于REC的等价性定理.     

基于模板有限自动机的正则表达式匹配算法

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题,提出了模板有限自动机分组算法,基于规则模板对规则集进行分组,各分组分别构建匹配引擎。同时,根据实际规则数目和系统结构对规则子集的数目改变,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。     

AG: A set of Maple Packages for Manipulating Automata and Semigroups

AG is a set of packages for manipulating finite state automata and finite semigroups. This software includes on the one hand the AUTOMAP package which affords the usual operations on automata (union, concatenation, Kleene closure,.) as well as the usual transformations (trimming, minimization,.) and on the other hand the GREEN package which yields the (regular or not) D-class structure of a finite monoid. The AG software has been implemented using the Maple symbolic computation system. ©1997 by John Wiley & Sons, Ltd.     

基于量子逻辑的下推自动机与上下文无关文法

给出基于量子逻辑的下推自动机(e-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的e-VPDA与状态转移为分明函数且具有量子终态的e-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(e-VCFG)的等价性.     

量子自动机的刻画

澄清了各类量子自动机之间的相互关系,并给出了量子自动机的各种等价刻画定理.引入G-量子自动机、g-量子自动机、(广义)量子自动机及G-量子文法和g-量子文法,并阐明了它们与其他量子自动机之间的等价关系.在一定条件下讨论了G(g)-量子自动机与G(g)-量子文法的等价性,从而解决了关于量子文法产生量子正规语言的问题.讨论了量子语言与正规语言的关系,特别是回答了Gudder提出的两个公开问题.最后,给出了一种减少状态空间维数的方法.     

模糊有穷自动机与单体二阶Lukasiewicz逻辑

该文引入了单体二阶Lukasiewicz逻辑,进而给出了模糊有穷自动机识别语言的逻辑描述,证明了多值逻辑意义下的Bchi与Elgot基本定理.通过引入星-自由模糊语言与非周期模糊语言,刻画了可以用一阶Lukasiewicz逻辑定义的模糊语言.     

基于量子逻辑的自动机理论的拓扑性质

研究了基于量子逻辑的自动机理论(简称l-值自动机理论)的拓扑性质.给出了successor算子和source算子的另一种定义,讨论了successor算子、source算子和l-值子自动机之间的关系,得到了successor算子、source算子和l-值子自动机的某种等价性.进一步描述了由successor算子、source算子和l-值子自动机来构造拓扑.得出了successor算子、source算子和l-值子自动机的一些基本性质,证明了在&关于(分配时,successor算子、source算子以及l-值子自动机的某些特殊性质.因而得到了由它们构造拓扑的一个较弱的条件,并且澄清了三者构造拓扑时的等价性.     

Towards a Formal Semantics for UML/MARTE State Machines Based on Hierarchical Timed Automata

UML is a widely-used,general purpose modeling language.But its lack of a rigorous semantics forbids the thorough analysis of designed solution,and thus precludes the discovery of significant problems at design time.To bridge the gap,the paper investigates the underlying semantics of UML state machine diagrams,along with the time-related modeling elements of MARTE,the profile for modeling and analysis of real-time embedded systems,and proposes a formal operational semantics based on extended hierarchical timed automata.The approach is exemplified on a simple example taken from the automotive domain.Verification is accomplished by translating designed models into the input language of the UPPAAL model checker.     

实时时序逻辑语言XYZ/RE到时间自动机的映射

时间自动机是一种重要的实时系统建模工具。本文建立了实时时序逻辑语言XYZ/RE到时间自动机的一种映射机制,将XYZ/RE所描述的系统进程直接转换为时间自动机,这样不但可以准确捕获实时系统功能和控制行为,还可以利用基于时间自动机的验证工具UPPAAL对XYZ/RE描述的系统正确性进行检测。最后本文通过一个实例的描述与检测,验证了映射机制的有效性。