下推自动机的状态转换图与下推自动机的化简

参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。

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

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

回溯自动机与多步回溯自动机的关系

本文给出确定的回溯自动机DTA 和确定的多步回溯自动机DMTA 所接受的语言类之间的关系L(DTA)L(DMTA).

下推格值自动机词的计算

在格半群意义下,提出基于词计算的下推格值自动机模型,它的输入是输入字母表的模糊子集,即词串,对应的是具有模糊性的自然语言.并研究下推格值自动机识别的格值词语言,利用格半群的性质证明了下推格值自动机基于词的计算可以通过基于值的计算实现.

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。

下推格值自动机接受词语言两种方式的等价性

在格半群框架下,针对下推格值自动机模型的特点,提出其两种接受词语言的方式,并利用格半群的代数性质和自动机理论,证明了这两种方式接受词语言的等价性.

Fuzzy下推自动机与Fuzzy上下文无关语言的关系

在文献 (JournalofUESTofChina ,1992 ,2 1( 2 ) :188～ 190 )基础上 ,讨论了Fuzzy下推自动机按两种不同方式所接受的语言类的等价性 ,进而研究了Fuzzy下推自动机所产生的语言与Fuzzy上下文无关语言的等价关系 。

Lukasiewicz逻辑值上下文无关语言的代数刻画

提出了基于Lukasiewicz逻辑的下推自动机(l-VPDA)的概念,从代数角度研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用模糊状态构造,证明了任意以终状态方式接受模糊语言的l-VPDA与状态转移为经典函数且具有l值模糊终状态的l-VPDA间的相互等价性;并证明任意以空栈方式接受模糊语言的l-VPDA与状态转移除一步转移为模糊的以外,其余都是经典函数的l-VPDA是相互等价的;详细研究了l-值模糊上下文无关语言的代数和层次刻画,以及对于正则运算的封闭性。

最大乘积型Fuzzy上下无关文法与下推自动机

在文献[1]的基础上,讨论了最大乘积型Fuzzy上下文无关文法与最大乘积型Fuzzy下推自动机的关系,即:由给定的最大乘积型Fuzzy上下文无关文法可构造一个最大乘积型Fuzzy下推自动机使得二者接受的语言集相同,反之亦然。从而达到自动识别语言的目的。

有无1墨水点亚对数空间限定交替式下推自动机之间的关系

该文引入 1墨水点 2方向交替式下推自动机 ,它是 1个具有额外能力的 2方向交替式下推自动机 ,能够用 1个墨水点在输入带上标记出最多 1个单元格。对具有 1个墨水点的和没有墨水点的亚对数空间限定交替式下推自动机之间的关系进行研究。实例证明了具有

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

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

人工免疫系统中淋巴细胞的下推自动机模型

有些淋巴细胞的构造模型,如r-邻域位线性构造模型,识别能力不够强,尤其对正则表达式缺乏识别能力。该文以下推自动机模型为原理,提出了一种自动机模型的淋巴细胞,这种淋巴细胞具有比有限自动机更强的识别能力,同时利用相近的入侵具有相似性这一点,引进了一个经验队列,配合HMM中状态转移概率的概念,对状态转移进行评判。最后给出了模型具体的设计方案。

亚对数空间限定的多墨水点交替式下推自动机的闭包属性

交替式下推自动机是并行计算的一种模型,它的空间计算复杂性研究对于解明并行算法的内存消耗具有重要意义。复杂性语言族的闭包属性反映了具有一定复杂性空间的并行计算模型之间的组合关系。论文研究仅有全称状态的交替式下推自动机的闭包属性,这些自动机均具有多个墨水点和亚对数限定的存储空间.通过设立巧妙的证人语言,本文使用反证法证明了具有有限多个墨水点的仅有全称状态的交替式下推自动机在星号、保持长度的同态、以及与正则语言的连结等运算下是不封闭的。

A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential （Universal） States

1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input （with an inkdot） once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential （universal） states, and shows, for example, that for any function L（n） such that L（n） ≥ log logn and L（n） = o（log n）, the class of sets accepted by weakly （strongly） L（n） space-bounded 1-inkdot two-way alternating pushdown automata with only existential （universal） states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure.

下推自动机的半环方法

文章介绍半环代数理论,讨论了下推自动机,在下推自动机概念的基础上给出了其在半环上的定义,特别是下推转换矩阵的引入,使下推自动机的行为和半环代数理论上的等式建立了联系.从而使下推自动的讨论更加简洁.

一种针对正规树模式的复杂事件查询方法

随着对半结构化流式数据进行复杂事件查询的需求日益增加,高效地进行复杂事件查询显得尤为重要。目前针对复杂事件查询的方法主要集中在仅有结构约束的查询请求,对同时含有时序约束的查询请求不能很好地支持。因此,针对XML这种半结构化流式数据,提出了一种基于下推自动机扩展的模式匹配算法,它能够高效地处理使用正规树模式描述的含有结构约束和时序约束的复杂事件,通过对比实验也证明了该方法具有更高的性能。

基于完备剩余格值逻辑的下推自动机与上下文无关文法

引入了L-值下推自动机的概念,讨论了L-值下推自动机按2种不同方式所接受的语言类的等价性,并指出了它能识别L-值正则语言。利用广义的子集构造方法,证明了一般的L-值下推自动机与状态转移为分明函数且具有L-值终态的L-值下推自动机的等价性。通过此等价性,给出了L-值上下文无关语言的代数刻画和层次刻画,并证明了L-值上下文无关语言关于正则运算的封闭性。另外,提出了L-值上下文无关文法的概念,给出了与之等价的且带有经典开始符的L-值上下文无关文法。借此等价关系,讨论了L-值下推自动机与L-值上下文无关文法是等价的,并说明了在完备剩余格值逻辑意义下,可采用最左派生、最右派生、Chomsky范式或者Greibach范式中的任何一种来生成L-值上下文无关语言。