数理解析研究所講究録
第 1799 巻 2012 年 179-182

179

Automata inspired by biochemical reaction*

早稲田大学大学院教育学研究科 大久保 文哉 (Fumiya Okubo)
Graduate School of Education, Waseda University

電気通信大学大学院電気通信学研究科 小林 聡 (Satoshi Kobayashi)
Graduate School of Informatics and Engineering, University of Electro-Communications

早稲田大学教育総合科学学術院 横森 貴 (Takashi Yokomori)
Department of Mathematics, Faculty of Education and Integrated Arts and Sciences,

Waseda University1

Introduction

This paper is organized as follows. After preparing the basic notions and notations in Section 2,
we introduce the main notion of reaction automata
together with one language example in Section 3.
Moreover we present our main results: reaction
automata are computationally universal. We also

Motivated by two notions of a reaction system([3, 4, 5]) and a multiset ([1]), in this paper wewill introduce computing devices called reaction
automata and show that they are computationallyuniversal by proving that any recursively enumerconsider some subclasses of reaction automata fromable language is accepted by a reaction automaton.
a viewpoint of the complexity theory in Section 4,
There are two points to be remarked: On one hand,and investigate the language classes accepted by
the notion of reaction automata may be taken as
those subclasses in comparison to the Chomsky hia kind of an extension of reaction systems in theerarchy. Finally, concluding remarks as well as fusense that our reaction automata deal with multure research topics are discussed in Section 5.
tisets rather than (usual) sets as reaction systems
do, in the sequence of computational process. On
2 Preliminaries
the other hand, however, reaction automata are inWe assume that the reader is familiar with thetroduced as computing devices that accept the setsof string objects (i.e., languages over an alphabet). basic notions of formal language theory. For unexThis unique feature, i.e., a string accepting device plained details, refer to [8].
We use the basic notations regarding multisets
based on multiset computing in the biochemical rethat
follow [2, 9]. A multiset over an alphabet $V$
action model can be realized by introducing a sim: a mapping : $Varrow N$ , where $N$ is the set ofple idea of feeding an input to the device from the is:
integers and for each $a\in V,$ $\mu(a)$non-negativeenvironment.
epresents the number of occurrences of in the*The work of F. Okubo was in part supported by Waseda multiset . The set of all multisets over $V$ is deUniversity Grant for Special Research Projects: $2011A-842$ . noted by $V\#$ , including
the empty multiset denoted
The work of S. Kobayashi was in part supported by Grants, where $\mu_{\lambda}(a)=0$ for all $a\in V$ . We often
in-Aid for Scientific Research (C) No.22500010, Japan Soci- byety for the Promotion of Science. The work of T. Yokomoriwas in part supported by Waseda University Grant for Spe- identify a multiset with its string representation
cial Research Projects: $2011B-056$ .
1
or any permutation of.
$\mu$

$a$

$1$

$J$

$\mu$

$J$

$\rceil$$\mu_{\lambda}$

$i$

$\mu$

$w_{\mu}=a_{1}^{\mu(a_{1})}\cdots a_{n}^{\mu(a_{\mathfrak{n}})}$$w_{\mu}$

180
A usual set
is regarded as a multiset$\mu_{U}(a)=1$
if is in and $\mu_{U}(a)=0$
such thatotherwise. In particular, for each symbol $a\in V$ , ais often denoted by itself.
multisetover , we define one
For two multisets
relation and three operations as follows:$U\subseteq V$$\mu_{U}$

$U$

$a$

$a$

$\mu\{a\}$$\mu_{1},$Incl usion :Sum:Intersection :Difference :$\mu_{1}\subseteq\mu_{2}$$V$$\mu_{2}$iff $\mu_{1}(a)\leq\mu_{2}(a)$ ,$(\mu_{1}+\mu_{2})(a)=\mu_{1}(a)+\mu_{2}(a)$$\beta\in A^{*}$$\alpha\subset\beta$$\alpha$$T$$\beta$$En_{A}^{p}(T)$

$T$

$A$

,

$T$

${\rm Res}_{A}(T)$${\rm Res}_{A}(T)=\{T-R_{o}+P_{\alpha}|\alpha\in En_{A}^{p}(T)\}$$( \mu_{1}\cap\mu_{2})(a)=\min\{\mu_{1}(a)_{:}\mu_{2}(a)\}$$(\mu_{1}-\mu_{2})(a)=\mu_{1}(a)-\mu_{2}(a)$, and andsuch that
if there is no.
byare enabled
we denote the set of all multisets(3) By$\alpha\in A\#$inwhich are enabled byof reactions
maximally parallel manner.
, is(4) The results of on , denoted bydefined ae follows:,,Note that we have ${\rm Res}_{A}(T)=\{T\}$ if.

$En_{A}^{p}(T)=\emptyset$.

Definition 3. (Reaction Automata) A reacis a 5-tuple
tion automaton (RA)for each $a\in V$ . The sum for a family of multisets $(S, \Sigma, A, D_{0}, f)$ , where. For a multiset
is denoted by
is a finite set, called the background set of
and $n\in N,$
is defined by $\mu^{n}(a)=n\cdot\mu(a)$ for,each $a\in V$ . The weight of a multiset is $|\mu|=$.
is called the input alphabet of ,(for the case$\mu_{2}\subseteq\mu_{1}$only),$\mathcal{A}$$\mathcal{A}$$\mathcal{M}=\{\mu_{i}\}_{*\in I}$

.
.
.
.
.

$\sum_{:\in I}\mu;$$\mu^{n}$

$\mu$

$\mu$

$\sum_{a\in V}\mu(a)$3Reaction Automata

$=$

$S$

$\mathcal{A}$$\mathcal{A}$$\Sigma(\subseteq S)$$A$

is a finite set of reactions in$S$,$D_{0}\in s\#$ is an initial multiset,
By recallin from [3] basic notions related to re$f\in S$ is a special symbol which indicates theactions systems, we first extend them (defined onfinal state.
the sets) to the notions on the multisets. Then,
we shall introduce our notion of reaction automata Definition 4. Let $A=(S, \Sigma, A,D_{0}, f)$ be an RA
which plays a central role in this paper.
and $w=a_{1}\cdots a_{n}\in\Sigma$ “. An interactive prois an infinite sequencewith input
cess inDefinition 1. For a set , a reaction in is a 3$\pi=D_{0},$, wheretuple $a=(R_{a},I_{a},P_{a})$ of finite multisets, such that
$R_{a},P_{a}\in S^{*},$.
and$g$$w$$\mathcal{A}$

$S$

$S$

$\ldots,$$D_{i},$$\ldots$$R_{a}\cap I_{a}=\emptyset$$I_{a}\subseteq S$$\{\begin{array}{ll}D_{1+1}\in{\rm Res}_{A}(a_{i+1}+D_{i}) (for 0\leq i\leq n-1),D_{l+1}\in{\rm Res}_{A}(D_{i}) (for an i\geq n).\end{array}$The multisets
are called the reactant
and
we denote the set of all interactiveof a and the product of , respectively, while the set By$A$
is called the inhibitor of . These notations are processes in with input .
extended to a multiset of reactions as follows: For
In order to represent an interactive process ,a set of reactions and a multiset over ,we also use the ”arrow notation” for :$P_{a}$$R_{a}$$IP(\mathcal{A}, w)$

$a$

$w$

$a$

$I_{a}$

$\pi$

$A$

$\alpha$

$A$

$\pi$

.

$D_{1}arrow a_{2}\ldotsarrow^{a_{n}}D_{n}arrow D_{n+1}arrow\cdots$$D_{0}arrow a_{1}$.

For an interactive process in $A$ with input $w$ ,for some $m\geq|w|$ , then we have
ifDefinition 2. Let be a set of reactions in and${\rmRes}_{A}(D_{m})=\{D_{m}\}$and $D_{m}=D_{m+1}=\cdots$ .
that$\alpha\in A\#$be a multiset of reactions over . Then,In this case, considering the smallest $m$ , we say thatfor a finite multiset $T\in s\#$ , we say that(at the mth step). When anconverges on,(1) is enabled by ifand, eachofinteractive process converges on(2) is enabled by in maximally paralld manneris omitted for $i\geq m+1$ .
$R_{\alpha}= \sum_{a\in A}R_{a}^{\alpha(a)},$$I_{\alpha}= \bigcup_{a\subseteq\alpha}I_{a},$$P_{\alpha}= \sum_{a\in A}P_{a}^{\alpha(a)}$$\pi$$En_{A}^{p}(D_{m})=\emptyset$

$S$

$A$

$A$

$\pi$

$\alpha$$T$$R_{\alpha}\subseteq T$$D_{m}$$I_{\alpha}\cap T=\emptyset$$\pi$$\alpha$

$T$

$\pi$

$D_{m}$$D_{:}$

181
Definition 5. Let $A=(S, \Sigma, A, D_{0}, f)$ be an RA.
Let be an RA and be a function defined on
The language accepted by , denoted by, is N. Motivated by the notion of a workspace fordefined as follows:a phrase-structure grammar ([8]), we define: for,with $n=|w|$ , and for in$L(\mathcal{A})=\{w\in\Sigma^{*}|\pi\in IP(A, w)$ that converges on$WS(w, \pi)=\max_{i}$ { $|D_{i}||D_{i}$ appears in}.
at the m-th step, for some$f$$\mathcal{A}$$L(\mathcal{A})$$\mathcal{A}$$w\in L(\mathcal{A})$$IP(\mathcal{A}, w)$

$\pi$

$\pi$

$D_{m}$$m\geq|w|$, and$f\subseteq D_{m}$}.

Further, the workspace of

Example 1. Let us consider a reaction automaton
defined as follows:$\mathcal{A}$

for

$w$

is defined as:$WS(w,A)= \min_{\pi}\{WS(w, \pi)|\pi\in IP(A, w)$ ,$\mathcal{A}=(S, \Sigma, A, D_{0}, f)$$S=\{a,b, c, d, e, f\}$with$\Sigma=\{a\}$where$\pi$converges.}.

,Definition 6. (i). An RA is $f(n)$ -bounded if forwith $n=|w|,$ $WS(w,A)$ is boundedany$a_{2}=(b^{2}, ac,c),$ $a_{3}=(c^{2}, b, b)$ ,by $f(n)$ .
$a_{4}=(bd,$ $ac,$ $e),$ $a_{5}=(cd,$, 下 6 $=(e,$ $abc,$ $f)$ , (ii). If a function $f(n)$ is a constant(linear, polynomial, exponential), then$D_{0}=d$ .
is termed
k-bounded (resp. linearly-bounded, polynomiallyLet $w=$ aaaaaaaa
be the input string and bounded, exponentially-bounded), and denoted byconsider an interactive process such thatk-RA (resp. lin-RA, poly-RA, exp-RA). Further,
the class of languages accepted by k-RA (lin-RA,: $darrow^{a}adarrow^{a}bdarrow^{a}abdarrow^{a}b^{2}darrow^{a}ab^{2}d$poly-RA, exp-RA, arbitrary RA) is denoted by k$arrow^{a}b^{3}darrow^{a}ab^{3}darrow^{a}b^{4}darrow c^{2}darrow bdarrow earrow f$ .
resp.
.
$\mathcal{A}$$A=\{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}\}$, where$w\in L(\mathcal{A})$$a_{1}=(a^{2}, \emptyset, b),$$b,$ $e)$$k$$\mathcal{A}$$\in S^{*}$

$\pi$

$\pi$

$\mathcal{R}A$$($$\mathcal{L}\mathcal{R}\mathcal{A},\mathcal{P}\mathcal{R}\mathcal{A},\mathcal{E}\mathcal{R}A,\mathcal{R}\mathcal{A})$It can be easily seen thatand $w\in$theLet us denote by. For instance, since, it holds class of regular (resp. linear, context-hee, contextthat. Hence, the stepsens $ve,$ recurs vely enumerable) languages.
is valid. We can also see that $L(\mathcal{A})=\{a^{2}" |n\geq 1\}$
We show two characterizations concerningwhich is context-sensitive (see Figure $1-(i)$ ).
in relation to the Chomsky hierarch.,
andWe shall show the equivalence of the accepting a nd two interesting results. One is concerned within terms
powers between reaction machines and Turing ma- a representation theorem for the class,anew
theotherisofandcharacterizationofchines. For the details of proof, we refer [6].
$CS$ with(for the proofs, see [7]).
Theorem 1. Every recursively enumerable lanTheorem 2. For any recursively enumerable language is accepted by a reaction automaton.
guage , there exists an $LRA$ $A$ such that $L=$1for some projection .
$\pi\in IP(\mathcal{A}, w)$$\mathcal{R}\mathcal{E}\mathcal{G}(\mathcal{L}\mathcal{I}\mathcal{N},C\mathcal{F},CS,\mathcal{R}\mathcal{E})$$a_{2}^{2}\in En_{A}^{p}(b^{4}d)$$L(\mathcal{A})$$|$$c^{2}d\in{\rm Res}_{A}(b^{4}d)$$b^{4}darrow c^{2}d$’$\mathcal{L}\mathcal{R}\mathcal{A}$$\mathcal{E}\mathcal{R}\mathcal{A}$$\}$$\mathcal{R}\mathcal{E}$$($$\mathcal{L}\mathcal{R}\mathcal{A}$$\mathcal{E}\mathcal{R}\mathcal{A}$$\langle$$r$$($4Space Complexity Classes

$L$

$h$

$h(L(\mathcal{A}))$

Theorem 3. The following inclusions hold:We now consider space complexity issues of re(1).
.
action automata. That is, we introduce some(2).
subclasses of reaction automata and investigate(for each $k\geq 1$ ).
the relationships between classes of languages ac(3).
are incomparable.
andcepted by those subclasses of automata and language classes in the Chomsky hierarchy.
$r$$($$($$CS=\mathcal{E}\mathcal{R}\mathcal{A}$$\mathcal{R}\mathcal{E}\mathcal{G}=k-\mathcal{R}\mathcal{A}\subset \mathcal{L}\mathcal{R}\mathcal{A}\subseteq\prime P\mathcal{R}\mathcal{A}\subset \mathcal{E}\mathcal{R}\mathcal{A}\subset$$’)$$\mathcal{R}\mathcal{A}=\mathfrak{X}$$($$\mathcal{L}\mathcal{I}\mathcal{N}(C\mathcal{F})$$\mathcal{L}\mathcal{R}\mathcal{A}$182

図 1: (i) Interactive processes for accepting

Chomsky hierarchy :5$a^{2},$$a^{4}$and$a^{8}$

in$\mathcal{A}$. (ii) Language class relations in the.

$L_{1}=\{a^{n}b^{n}c^{n}|n\geq 0\};L_{2}=\{a^{m}b^{m}c^{n}ff^{\iota}|m,n\geq 0\};L_{3}=\{ww^{R}|w\in\{a, b\}^{*}\}$

Concluding Remarks

2235, Springer, 2001.
[2] Gh. Paun, G. Rozenberg, A. Salomaa (Eds.),
Handbook of Membrvnne Computing, OxfordUniversity Press, 2010.

Reaction[3] A. Ehrenfeucht, G. Rozenberg,systems, Ibndamenta Informaticae vol.75,
pp.263-280, 2007.
[4] A. Ehrenfeucht, G. Rozenberg, Events andmodules in reaction systems, Theoretical Computer Science vol.376, pp.3-16, 2007.

[5] A. Ehrenfeucht, G. Rozenberg, Introducing
time in reaction systems, Theoretical Computer Science vol.410, pp.310-322, 2009.
[6] F. Okubo, S. Kobayashi, T. Yokomori, Reaction Automata, arXiv:1201. $3082v2$ , to appear
in Theoretical Computer Science.

[7] F. Okubo, S. Kobayashi, T. Yokomori,On the Properties of Language Classes
Defined by Bounded Reaction Automata,arXiv: 1111. $5038v2$ .
[8] A. Salomaa, Formal Languages, AcademicPress, New York, 1973.

参考文献[1] C. Calude, Gh.
, G. Rozenberg and A.
Salomaa (Eds.), Multiset Processing, LNCS
$P\dot{a}un$[9] Y. Suzuki, Y. FMjiwara, J. Talabayashi, H.
Tanaka, AItificial Life Applications of a Classof P Systems, in: Multiset Processing, C.
un, G. Rozenberg, A. SaloCalude, Gh.
maa (Eds.), LNCS 2235, Springer, pp.299-346,$P\dot{a}$2001.