Theory of reaction automata: a survey
Theory of reaction automata: a survey
复制标题
反应自动机理论：调查
DOI：
10.1007/s41965-021-00070-6
复制
发表时间：
2021
影响因子：
3.8
通讯作者：
Okubo Fumiya
中科院分区：
文献类型：
--
作者：
Yokomori Takashi;Okubo Fumiya
本文综述了反应自动机理论，对自然界中发生的生命反应的生化行为进行了建模和分析。受Ehrenfeucht和Rozenberg在2007年提出的反应系统和多集合的两个概念的启发，反应自动机(RAS)被提出作为接受字符串语言的计算模型。在给定输入符号序列的情况下，RA执行其计算过程如下：在每次接收输入符号时，它通过以规定的方式将反应规则应用于多集来改变当前配置(由多集表示)，其中考虑了两种应用方式：最大并行方式和(通常)顺序方式。RA用作扩展的有限自动机，其中多集扮演(无限数量)状态的角色，并且状态转移通过应用反应规则来执行。我们证明了RAS的计算能力在两种规则应用方式下都是图灵通用的。讨论了RA的空间有界变异体与Chomsky族之间的关系。进一步，我们讨论了化学反应自动机的概念，它是RAS的简化变体，具有不受抑制功能的反应规则。我们用各种相关的计算模型以及未来的研究课题来完成这一调查。
In this paper, we survey on reaction automata theory to model and analyze the biochemical behaviors of vital reactions occurring in nature. Inspired by two notions of a reaction system initiated by Ehrenfeucht and Rozenberg in 2007 and of a multiset, reaction automata (RAs) have been proposed as computing models for accepting string languages. Given an input sequence of symbols, an RA performs its computation process as follows: at every time of receiving an input symbol, it changes the current configuration (represented by a multiset) by applying reaction rules to the multiset in a prescribed manner, for which two kinds of application manners are considered: the maximally parallel manner and the (usual) sequential manner. An RA functions as an extended finite automaton in which multisets play a role of (unbounded number of) states and the state transition is performed by applying reaction rules. We show that the computational powers of RAs are Turing universal in both manners of rule applications. The relationship between the space-bounded variants of RA and the Chomsky hierarchy is also discussed. Further, we discuss the notion of chemical reaction automata, which is a simplified variant of RAs with reaction rules that are free from inhibitor functioning. We complete this survey with a variety of related models of computing together with future research topics.