Reaction Automata Working in Sequential Manner
Reaction Automata Working in Sequential Manner
复制标题
以顺序方式工作的反应自动机
DOI：
10.1051/ita/2013047
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Fumiya Okubo
中科院分区：
文献类型：
--
作者：
Fumiya Okubo
近年来，Escherichfeucht和Rozenberg引入了一个正式的模型，称为反应系统[5]，用于研究活细胞的功能，基于功能由生化反应之间的相互作用决定的想法，其中两个基本成分（反应物和抑制剂）作为控制相互作用的调节机制发挥关键作用。在[6]中，它表明，反应系统提供了一个正式的框架，适合于在抽象层面上调查的方式出现和进化的生化事件和模块。最近的论文继续在生物学和理论考虑的各种主题中研究反应系统，例如创建化合物的时间问题[7]，由反应系统定义的函数的组合性质[8，9，18]，反应系统的概率和量子变体[11]。在反应系统理论中，生化反应被表述为三元组a=（Ra，Ia，Pa），其中Ra是称为反应物的分子的集合，Ia是称为抑制剂的分子的集合，Pa是称为产物的分子的集合。设T是一组分子，将反应a应用于T的结果，记为resa（T），如果a被T使能，则由Pa给出（即，如果Ra包含在T中并且Ia与T不相交）。否则，结果为空。因此，如果在T上使能a，resa（T）= Pa，否则resa（T）= Pa。将应用反应a的结果推广到反应A的集合，记为resA（T），并适当地引入和研究了由resA（T）序列组成的交互过程。受反应系统概念的启发，在[15]中引入了反应自动机作为计算设备，并且通过证明所有递归可编程语言都被反应自动机接受，证明了它们在计算上是通用的。在[16]中，继续对反应自动机进行研究，重点关注反应自动机的空间有界类的形式语言理论性质。具体地说，它表明，所有的上下文敏感的语言是接受指数空间有界反应自动机。反应自动机的概念可以被看作是反应系统的一个扩展，在这个意义上，反应物和抑制剂被用作反应自动机的调节，但它们处理的是多集，而不是通常的反应系统。反应自动机是作为多集重写设备引入的，它接受字母表上的语言，其中这个功能是通过在计算的每个步骤将输入字符串的一个符号从环境馈送到设备的简单想法来实现的。从这个意义上讲，反应自动机也可以看作是Csuhaj− Varjú和Vaszil在[4]中引入的P自动机的简化变体，没有膜结构。我们不仅考虑了文献[15，16]中的最大并行方式，而且考虑了顺序方式作为规则应用的方式，并比较了反应自动机及其空间有界变体在上述两种方式下的计算能力。本文还研究了具有λ-移动的反应自动机（在[16]中引入）的顺序移动。此外，我们还探索了
In recent years, Ehrenfeucht and Rozenberg have introduced a formal model, called reaction systems [5], for investigating the functioning of the living cell, based on the idea that the functioning is decided by interactions between biochemical reactions, where two basic components (reactants and inhibitors) play a key role as a regulation mechanism in controlling interactions. In [6], it is shown that reaction systems provide a formal framework suited for investigating in an abstract level the way of emergence and evolution of biochemical events and modules. Recent papers continue the investigation of reaction systems in various topics motivated by biological and theoretical considerations, such as the issue of times for creating compounds [7], combinatorial properties of functions defined by reaction systems [8, 9, 18], probabilistic and quantum variants of reaction systems [11]. In the theory of reaction systems, a biochemical reaction is formulated as a triple a=(Ra, Ia, Pa), where Ra is the set of molecules called reactants, Ia is the set of molecules called inhibitors, and Pa is the set of molecules called products. Let T be a set of molecules, and the result of applying a reaction a to T, denoted by resa (T), is given by Pa if a is enabled by T (ie, if Ra is included in T and Ia is disjoint with T). Otherwise, the result is empty. Thus, resa (T)= Pa if a is enabled on T, and resa (T)=∅ otherwise. The result of applying a reaction a is extended to the set of reactions A, denoted by resA (T), and an interactive process consisting of a sequence of resA (T)’s is properly introduced and investigated. Inspired by the notion of reaction systems, reaction automata have been introduced in [15] as computing devices, and it has been shown that they are computationally universal by proving that all recursively enumerable languages are accepted by reaction automata. In [16], the investigation with reaction automata is continued with a focus on the formal language theoretic properties of spacebounded classes of reaction automata. Specifically, it is shown that all contextsensitive languages are accepted by exponential space bounded reaction automata. The notion of reaction automata may be regarded as an extension of reaction systems in the sense that reactants and inhibitors are employed as regulation in reaction automata, however they deal with multisets rather than usual sets as reaction systems do. Reaction automata are introduced as multiset rewriting devices that accept languages over an alphabet, where this feature is realized by a simple idea of feeding one symbol of an input string at each step of computation, to the device from the environment. In this sense, reaction automata may also be regarded as simplified variants of P automata introduced by Csuhaj− Varjú and Vaszil in [4] with no membrane structure.In this paper, we continue the investigation of reaction automata with a focus on the way of rule application. We consider not only maximally parallel manner employed in [15, 16], but also sequential manner as the way of rule application, and compare the computational powers of reaction automata and their spacebounded variants in the above two manners. Reaction automata with λ-moves (introduced in [16]) in sequential manner are also investigated. Further, we explore a