哈密顿路径问题的一种基于有穷自动机的DNA算法

提出了一种基于有穷自动机的解决哈密顿路径问题的DNA算法,将有穷自动机的状态用含有DNA限制性内切酶的识别位点的DNA双链分子来编码,通过限制性内切酶的生物化学反应来实现状态的转移。算法的创新之处在于用DNA计算模拟有穷自动机的运行过程中,保留了其经过的各个状态,以便最后筛选出经过各个顶点的路径。算法的优点是实验实现简易,大大减少所使用的DNA分子的数量。     

用于信息加密的分子自动机的编码研究

利用DNA计算的方法构造的分子自动机是一种纳米尺度的计算机构，它能在纳米尺度进行高度并行的逻辑、推理等运算，从而实现自动机的功能，是一种DNA计算和纳米计算的新模型。由于有限自动机可以用于信息加密和解密，因此分子有限自动机也可以实现类似的功能。通过对分子有限自动机进行合理的编码，可实现一种新型信息加密和解密的方法。     

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

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

基于有限状态自动机的服务组合模型

分析了目前服务计算的研究现状和存在的问题，在D Berardi和A Wombacher的基础上提出了一种带条件的有限状态自动机模型cFSA（Finite State Automata with condition），并给出了基于cFSA的服务理论模型．在该服务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型，并给出了该模型的代数性质和实现方法．     

BPEL中基于有限状态自动机的Web服务自动组合

提出了一种基于有限状态自动机的Web服务自动组合方法,该方法能够自动实现BPEL中抽象业务流程与Web服务的绑定.以有限状态自动机模型形式化地定义了业务流程的外模式和内模式,将Web服务组合问题转化为有限状态自动机问题.利用有限状态自动机的笛卡儿积运算,得出了服务组合系统的行为描述.在此基础上,提出了组合服务存在性的判定依据,进一步给出了组合服务的计算方法,设计并实现了一个演示系统.     

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

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

基于FSA的DNA重复体频率统计算法

针对现有DNA重复体频率统计算法效率低、灵活性差等不足,基于字符串多模式匹配的有限状态自动机,构造DNA子序列比对自动机,利用KMP算法对自动机进行状态转移优化,由此提出一种高效的重复体频率统计算法。该算法通过对DNA数据库的线性扫描,得到每个DNA子序列在全局数据库中重叠与非重叠的重复体频率统计信息以及指定DNA序列集合的最长公共子序列信息。实验结果表明,该算法具有效率高、匹配精确、信息获取方式灵活、支持在线操作等优势。     

基于弹性滑窗FFT的用电设备在线状态监测研究与应用

基于负荷特征的用电设备在线状态监测是当前研究与应用的热点。首先基于有限状态自动机提出用电设备的状态行为模型,可以有效地描述用电设备运行时的稳态与暂态特征;其次,提出一种弹性滑窗FFT算法,解决了滑窗FFT只适用于固定频率下进行频谱计算的问题;最后,实现一个针对该模型中频谱特征实时计算的用电设备在线状态监测系统原型,验证了上述模型和算法的有效性。     

一种基于模型检测的二进制程序脆弱性分析框架

针对二进制程序脆弱性分析的实际需求,提出了一种基于模型检测的二进制程序脆弱性分析框架。首先定义了二进制程序的抽象模型,描述了基于有限状态自动机的软件脆弱性形式化表示和基于事件系统的软件安全属性表示方法。在此基础上,提出了基于模型检测的脆弱性分析过程和算法。根据该分析框架,设计并实现了二进制程序脆弱性分析工具原型。通过脆弱性分析实验,详细说明了该框架的工作原理,验证了该分析方法的有效性。     

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

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

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.     

A note on deciding controllability in pushdown systems

Consider an event alphabet /spl Sigma/. The supervisory control theory of Ramadge and Wonham asks the question, given a plant model G, with language K L/sub M/(G)/spl sube//spl Sigma//sup */ and another language K/spl sube/ L/sub M/(G), is there a supervisor /spl psi/ such that L/sub M/(/spl psi//G)=K. Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of K with respect to L/sub M/(G). They showed that when G is a finite state automaton and K is a regular language (also generated by a finite state automaton), then the controllability property was decidable for K. The class of languages generated by pushdown automata properly includes the regular languages. They are accepted by finite state machines coupled with pushdown stack memory. This makes them interesting candidates as supervisory languages, since the supervisor will have nonfinite memory. In this note, we show the following: i) If S is a specification given by a deterministic pushdown automaton and L is generated by a finite state machine, then there is an algorithm to decide whether K=S/spl cap/L is controllable with respect to L. ii) It is undecidable for an arbitrary specification S generated by a nondeterministic pushdown automaton and plant language L generated by a finite state machine whether K=S/spl cap/L is controllable with respect to L.     

A saturation method for the modal μ-calculus over pushdown systems

We present an algorithm for computing directly the denotation of a μ-calculus formula χ over the configuration graph of a pushdown system. Our method gives the first extension of the saturation technique to the full μ-calculus. Finite word automata are used to represent sets of pushdown configurations. Starting from an initial automaton, we perform a series of automaton manipulations which compute the denotation by recursion over the structure of the formula. We introduce notions of under-approximation (soundness) and over-approximation (completeness) that apply to automaton transitions rather than runs. Our algorithm is relatively simple and direct, and avoids an immediate exponential blow up. Finally, we show experimentally that the direct algorithm is more efficient than via a reduction to parity games.     

Pushdown Processes: Games and Model-Checking

A pushdown game is a two player perfect information infinite game on a transition graph of a pushdown automaton. A winning condition in such a game is defined in terms of states appearing infinitely often in the play. It is shown that if there is a winning strategy in a pushdown game then there is a winning strategy realized by a pushdown automaton. An EXPTIME procedure for finding a winner in a pushdown game is presented. The procedure is then used to solve the model-checking problem for the pushdown processes and the propositional μ-calculus. The problem is shown to be DEXPTIME-complete.     

Reversible pushdown automata

Reversible pushdown automata are deterministic pushdown automata that are also backward deterministic. Therefore, they have the property that any configuration occurring in any computation has exactly one predecessor. In this paper, the computational capacity of reversible computations in pushdown automata is investigated and turns out to lie properly in between the regular and deterministic context-free languages. Furthermore, it is shown that a deterministic context-free language cannot be accepted reversibly if more than realtime is necessary for acceptance. Closure properties as well as decidability questions for reversible pushdown automata are studied. Finally, we show that the problem to decide whether a given nondeterministic or deterministic pushdown automaton is reversible is P-complete, whereas it is undecidable whether the language accepted by a given nondeterministic pushdown automaton is reversible.     

On dynamics of automata with a stack

In this paper we introduce a new dynamical system of a pushdown automaton, called automaton with a stack (AS). We prove that every AS has a periodic configuration by construction of it. Next, we define a special case of an AS, called AS with finite memory and we prove that the AS has a finite memory if and only if it is positively expansive. Furthermore, we prove that every AS with finite memory has shadowing property. Having these two properties, we set a finite-to-one map between an AS with finite memory and some vertex subshift, which gives us a semi-conjugacy between these two systems. Additionally, we define an algorithm to decide if a given graph G describes some AS with finite memory and to calculate maximal depth of a stack.     

Measuring nondeterminism in pushdown automata

The amount of nondeterminism that a pushdown automaton requires to recognize an input string can be measured by the minimum number of guesses that it must make to accept the string, where guesses are measured in bits of information. When this quantity is unbounded, the rate at which it grows as the length of the string increases serves as a measure of the pushdown automaton's “rate of consumption” of nondeterminism. We show that this measure is similar to other complexity measures in that it gives rise to an infinite hierarchy of complexity classes of context-free languages differing in the amount of the resource (in this case, nondeterminism) that they require. In addition, we show that there are context-free languages that can only be recognized by a pushdown automaton whose nondeterminism grows linearly, resolving an open problem in the literature. In particular, the set of palindromes is such a language.     

A Note on the Properties of the Supremal Controllable Sublanguage in Pushdown Systems

Consider an event alphabet Sigma. The supervisory control theory of Ramadge and Wonham asks the question: given a plant model G with language L_M (G) sube Sigma* and another language K sube L_M (G), is there a supervisor phi such that L_M (phi/G) = K? Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of K with respect to L_M (G). They showed that when G is a finite-state automaton and K is a regular language (also generated by a finite state automaton), then there is a regular supremal controllable sublanguage sup_C (K) sube K that is effectively constructable from generators of K and G. In this paper, we show: 1) there is an algorithm to compute the supremal controllable sublanguage of a prefix closed K accepted by a deterministic pushdown automaton (DPDA) when the plant language is also prefix closed and accepted by a finite state automaton and 2) in this case, we show that this supremal controllable sublanguage is also accepted by a DPDA.     

On groups whose word problem is solved by a˜counter automaton

We prove that a group G has a word problem that is accepted by a deterministic counter automaton with a weak inverse property if and only if G is virtually abelian. We extend this result to larger classes of groups by considering a generalization of finite state automata, counter automata and pushdown automata. Natural corollaries of our general result include a restricted version of Herbst's classification of groups for which the word problem is a one counter language and a new classification of automata that accept context-free word problems.     

On distributed catenation

We introduce a new operation between words and languages, called distributed catenation. The distributed catenation is a natural extension of the well-known catenation operation. As for partial shuffle operation the introduction of this operation is motivated by the theory of concurrency. At the same time the distributed catenation is a powerful operation. For instance, any Turing machine can be simulated by a pushdown automaton that uses distributed catenation for the pushdown memory.