基于DNA计算的分子下推自动机(英文)

DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来推进计算过程．2001年以色列的Yaakov Benenson等人在基于DNA计算的发卡模型实现了具有状态转移功能的分子有限状态自动机,国内则有利用DNA计算的方法构造可编程分子下推存储器的相关研究．该存储器基于分子自动机的原理,能按一定逻辑进行自组装,是一种纳米尺度的生物存储机构．文中首先通过在分子有限自动机上扩展一个分子下推存储器从而获得了一种简单的分子下推自动机,并基于该下推自动机提出了一类语言的分子自动机解法．接着提出了两种改进的分子下推自动机的模型,通过增加模型复杂度,分别解决了基本型分子下推自动机存在输人字符串限制和输入分子形式不统一的问题．计算理论表明,该种下推自动机的计算能力超过了已有的有限自动机．     

下推自动机

5.1 非形式的描述 我们现在考虑一种装置——下推自动机,它在形式语言的研究中是十分重要的。此装置基本上是一个能控制一条输入带和一个下推存储器的有穷自动机。下推存储器是一种“先进后出”表,即符号的写入或取出只能在表的顶进行。当把一符号写到表的顶时,原来在顶的符号就变为从顶开始的第二个符号,而原来从顶     

确定的下推自动机

12.1 引言 我们曾看到不确定的下推自动机恰巧接受前后文无关语言,我们要问是否每一个前后文无关语言都能由确定的下推自动机接受。回答是否定的。然而,能由确定的pda(简称dpda)接受的cfl的子集是重要的。因为这些语言能够较之由定理11.1给出的n~3时间更快地认别。 让我们回顾确定的pda的定义。一确定的     

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

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

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

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

基于量子逻辑的下推自动机的代数刻画

首先,本文提出量子下推自动机（简记为L-VPDA）的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA间的相互等价性;其次详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。     

下推自动机的逻辑计算类型

本文是定义了(单向)下推自动机的逻辑计算类型,对逻辑计算类型进行了分类,并证明了它们都是线性时间界限的.     

基于DNA下推自动机二进制减法和乘法的实现

提出了基于DNA下推自动机二进制减法和乘法的实现方法.一位二进制借位减法,是通过预先构造好的DNA下推自动机模型在一个试管中以该模型的运行方式自动完成运算.m位二进制借位减法,是在一位二进制减法的基础上,按照从低位到高位的顺序,将低位产生的借位作为高位试管操作巾的输入符号串,从而完成高位的减法运算.两位二进制乘法中包含移位和加法操作,在两个试管中分别设计好DNA下推自动机模型,分别完成被乘数与乘数各位的移位操作,同时结合相应的生物操作,将其作为另一个试管加法操作中的输入符号串,则加法操作中产牛的结果即为所求.在此基础上,m位二进制乘法可通过移位操作的并行性和加法操作的串行性来完成运算.这些实现方法为DNA下推自动机实现基本的算术运算提供了比较完整的运算机制.     

模糊有限自动机的最小化算法优化

现有的模糊自动机最小化算法没有涉及到对模糊自动机状态的隶属度迁移和变化的讨论,优化的模糊自动机最小化算法弥补了这类算法的不足之处。该算法将模糊有限自动机首先转化为单个初始状态的模糊自动机,然后再将转化后的模糊自动机化简为最小模糊自动机,算法在转化过程中单独讨论了模糊自动机状态隶属度的转化方式,使得算法更加严谨和简化。     

格值有限自动机等价判定算法

引入了完备L-Fuzzy矩阵的概念,给出了基于格半群的模糊有限自动机的形式化定义,即完备格值有限自动机,研究了它的主要性质;给出了完备格值有限自动机的行为矩阵,从行为矩阵出发,给出了自动机状态等价和自动机等价的定义。最后,得到了该类自动机等价的判定算法。     

Methods for Quantitative Analysis of Probabilistic Pushdown Automata

We present several constructions and techniques which have recently been used to tackle the prob- lems of qualitative/quantitative analysis of probabilistic pushdown automata.     

On The Space Complexity Of Turn Bounded Pushdown Automata

A pushdown automaton is said to make a turn at a given instant if it changes at that instant from stack increasing to stack decreasing. Let \hbox{NPDA-TURN}(\,f(n)) and \hbox{DPDA-TURN}(\,f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f v ( n ) turns for any input of length n . In this paper the following inclusions that express the space complexity of turn bounded pushdown automata are given: \hbox{DPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log f(n)\log n) , and \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf NSPACE} (\log f(n)\log n) . In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: \hbox{DPDA-TURN}(O(1))\subseteq {\bf DL} and \hbox{NPDA-TURN}(O(1))\subseteq {\bf NL} , from which two corollaries follow: one is that the class of metalinear context-free languages is complete for NL , and the other is that a more tight inclusion \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log n) cannot be derived unless {\bf DL}={\bf NL} , though \hbox{NPDA-TURN} (\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log^2n) holds.     

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

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

Pushdown tree automata

We define topdown pushdown tree automata (PDTA's) which extend the usual string pushdown automata by allowing trees instead of strings in both the input and the stack. We prove that PDTA's recognize the class of context-free tree languages. (Quasi)realtime and deterministic PDTA's accept the classes of Greibach and deterministic tree languages, respectively. Finally, PDTA's are shown to be equivalent to restricted PDTA's, whose stack is linear: this both yields a more operational way of recognizing context-free tree languages and connects them with the class of indexed languages.     

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.     

Spinal-Formed Context-Free Tree Grammars

In this paper we introduce a restricted model of context-free tree grammars called spine grammars, and study their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It is shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduce acceptors called linear pushdown tree automata, and show that linear pushdown tree automata accept exactly the class of tree languages generated by spine grammars. Linear pushdown tree automata are obtained from pushdown tree automata with a restriction on duplicability for the pushdown stacks. Received May 29, 1998, and in revised form April 27, 1999, and in final form May 10, 1999.     

Deciding Emptiness for Stack Automata on Infinite Trees

We show that the emptiness problem for Büchi stack automata on infinite trees is decidable in elementary time. We first establish the decidability of the emptiness problem for pushdown automata on infinite trees. This is done using a pumping-like argument applied to computation trees. We then show how to reduce the emptiness problem for stack automata to the emptiness problem for pushdown automata. Elsewhere, we have used the result to establish the decidability of several versions of nonregular dynamic logic.