Automata
inspired
by
biochemical
reaction
*早稲田大学大学院教育学研究科
大久保 文哉(Fumiya Okubo)
GraduateSchool of Education, WasedaUniversity
電気通信大学大学院電気通信学研究科
小林 聡(Satoshi Kobayashi)
Graduate SchoolofInformaticsand Engineering, UniversityofElectro-Communications
早稲田大学教育総合科学学術院
横森 貴(Takashi Yokomori)
Department of Mathematics, Facultyof Education andIntegratedArts and Sciences,
WasedaUniversity
1
Introduction
Motivated by two notions of
a
reaction system([3, 4, 5]) and a multiset ([1]), in this paper we
will introduce computing devices called reaction
automataand show that they
are
computationallyuniversal by proving that anyrecursively
enumer-able language isaccepted bya reactionautomaton.
There
are
twopointsto be remarked: Ononehand,the notion of reaction automatamay be taken
as
a kind of an extension of reaction systems in the
sense
thatour
reaction automata deal withmul-tisets rather than (usual) sets
as
reaction systemsdo, in the sequenceofcomputationalprocess. On
the other hand, however, reactionautomata
are
in-troduced
as
computing devices thatacceptthesetsofstringobjects (i.e., languagesoveranalphabet).
This unique feature, i.e.,
a
string accepting devicebased
on
multiset computing in thebiochemicalre-action model
can
berealizedby introducinga
sim-pleidea of feeding
an
inputto the device from the :environment. :
$1$
*Theworkof F. Okubowasinpartsupported byWaseda $J$ University Grant forSpecialResearchProjects: $2011A-842$. $J$
The work ofS. Kobayashiwasinpartsupported by Grants-in-AidforScientific Research(C) No.22500010, Japan Soci- $\rceil$
ety for thePromotionofScience. Thework of T.Yokomori $i$
wasin partsupportedbyWaseda University Grant for Spe-cialResearchProjects: $2011B-056$. 1
Thispaperis organized
as
follows. Afterprepar-ing the basic notions and notations in Section 2,
weintroduce themain notion of reactionautomata
together with
one
languageexample in Section 3.Moreover
we
presentour
main results: reactionautomata
are
computationally universal. We alsoconsider
some
subclasses of reactionautomatafroma viewpoint ofthe complexity theory in Section 4,
and investigate the language classes accepted by
those subclassesin comparisonto the Chomsky
hi-erarchy. Finally, concluding remarks
as
wellas
fu-tureresearch topics
are
discussed inSection 5.2
Preliminaries
We
assume
that the reader is familiar with thebasicnotions of formal languagetheory. For
unex-plained details,refer to [8].
We
use
the basic notations regarding multisetsthat follow [2, 9]. A multiset
over an
alphabet $V$is a mapping $\mu$ : $Varrow N$, where $N$ is the set of
non-negative integers and for each $a\in V,$ $\mu(a)$
epresents the number of
occurrences
of $a$ in themultiset $\mu$. The set of all multisets
over
$V$ isde-noted by$V\#$, including the empty multiset denoted
by $\mu_{\lambda}$, where $\mu_{\lambda}(a)=0$for all $a\in V$
.
We oftenidentify
a
multiset $\mu$with its string representation$w_{\mu}=a_{1}^{\mu(a_{1})}\cdots a_{n}^{\mu(a_{\mathfrak{n}})}$ or any permutation of
$w_{\mu}$
.
数理解析研究所講究録
A usual set $U\subseteq V$ is regarded
as a
multiset $\mu_{U}$such that $\mu_{U}(a)=1$ if$a$ is in $U$ and $\mu_{U}(a)=0$
otherwise. In particular, for each symbol$a\in V$, a
multiset $\mu\{a\}$ isoften denoted by$a$ itself.
For two multisets $\mu_{1},$ $\mu_{2}$
over
$V$,we
defineone
relationand three operations
as
follows:Inclusion : $\mu_{1}\subseteq\mu_{2}$ iff $\mu_{1}(a)\leq\mu_{2}(a)$,
Sum: $(\mu_{1}+\mu_{2})(a)=\mu_{1}(a)+\mu_{2}(a)$,
Intersection: $( \mu_{1}\cap\mu_{2})(a)=\min\{\mu_{1}(a)_{:}\mu_{2}(a)\}$,
Difference
: $(\mu_{1}-\mu_{2})(a)=\mu_{1}(a)-\mu_{2}(a)$,(forthe
case
$\mu_{2}\subseteq\mu_{1}$ only),foreach $a\in V$
.
Thesum
fora
family of multisets$\mathcal{M}=\{\mu_{i}\}_{*\in I}$ isdenotedby$\sum_{:\in I}\mu;$
.
Fora
multiset$\mu$ and$n\in N,$ $\mu^{n}$ is defined by$\mu^{n}(a)=n\cdot\mu(a)$ for
each $a\in V$
.
The weight ofa
multiset $\mu$ is $|\mu|=$$\sum_{a\in V}\mu(a)$
.
3
Reaction Automata
By recallin$g$from [3] basicnotionsrelated to
re-actions systems, we first extend them (definedon
the sets) to the notions
on
the multisets. Then,we
shall introduceour
notion of reaction automatawhich plays
a
central role in this paper.Definition 1. For
a
set $S$,a
reaction in$S$isa
3-tuple$a=(R_{a},I_{a},P_{a})$ offinite multisets, suchthat
$R_{a},P_{a}\in S^{*},$ $I_{a}\subseteq S$and $R_{a}\cap I_{a}=\emptyset$
.
The multisets$R_{a}$ and$P_{a}$
are
called the reactantofaand the productof$a$, respectively, while theset
$I_{a}$iscalled the inhibitor of$a$
.
These notationsare
extended to
a
multiset ofreactionsas
follows: Fora
setofreactions$A$ anda
multiset $\alpha$over
$A$,$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)}$
.
Definition 2. Let$A$bea setofreactionsin$S$and
$\alpha\in A\#$ be
a
multiset of reactionsover
$A$.
Then,fora finitemultiset$T\in s\#$,
we
say that(1) $\alpha$is enabled by$T$if$R_{\alpha}\subseteq T$and$I_{\alpha}\cap T=\emptyset$,
(2) $\alpha$ is enabled by$T$ inmaximallyparalld
manner
ifthereis
no
$\beta\in A^{*}$ such that $\alpha\subset\beta$, and$\alpha$ and$\beta$
are
enabledby$T$.
(3) By $En_{A}^{p}(T)$
we
denote the set of all multisetsof reactions $\alpha\in A\#$ which
are
enabled by $T$ inmaximallyparallel
manner.
(4)Theresults
of
$A$ on$T$, denotedby${\rm Res}_{A}(T)$, isdefined aefollows:
${\rm Res}_{A}(T)=\{T-R_{o}+P_{\alpha}|\alpha\in En_{A}^{p}(T)\}$
.
Note that
we
have ${\rm Res}_{A}(T)=\{T\}$if$En_{A}^{p}(T)=\emptyset$.
Definition 3. (Reaction Automata) A
reac-tion automaton (RA) $\mathcal{A}$ is
a
5-tuple $\mathcal{A}$ $=$ $(S, \Sigma, A, D_{0}, f)$,where.
$S$ is afinite set, called the background setof
$\mathcal{A}$,
.
$\Sigma(\subseteq S)$is calledthe input alphabetof
$\mathcal{A}$,.
$A$isafinitesetof reactions in $S$,.
$D_{0}\in s\#$ isan
initialmultiset,.
$f\in S$ isa
special symbolwhich indicatesthefinal state.
Definition 4. Let $A=(S, \Sigma, A,D_{0}, f)$ be
an
RAand $w=a_{1}\cdots a_{n}\in\Sigma$“. An interactive
pro-cess in $\mathcal{A}$ with input $w$ is an infinite sequence $\pi=D_{0},$$\ldots,$$D_{i},$$\ldots$,where
$\{\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}$
By $IP(\mathcal{A}, w)$
we
denote the set of all interactiveprocessesin $A$with input$w$
.
In order to represent
an interactive
process $\pi$,we
alsouse
the ”arrow notation” for $\pi$ : $D_{0}arrow a_{1}$$D_{1}arrow a_{2}\ldotsarrow^{a_{n}}D_{n}arrow D_{n+1}arrow\cdots$
.
For
an
interactive process$\pi$in $A$with input$w$,if$En_{A}^{p}(D_{m})=\emptyset$ for
some
$m\geq|w|$, thenwe
havethat ${\rm Res}_{A}(D_{m})=\{D_{m}\}$ and $D_{m}=D_{m+1}=\cdots$
.
In thiscase,consideringthesmallest$m$,
we
saythat$\pi$ converges
on
$D_{m}$ (at the mthstep). Whenan
interactive process $\pi$converges
on
$D_{m}$, each $D_{:}$ of$\pi$isomitted for$i\geq m+1$
.
Definition 5. Let$A=(S, \Sigma, A, D_{0}, f)$ bean RA.
The language accepted by$\mathcal{A}$, denoted by $L(\mathcal{A})$, is
defined asfollows:
$L(\mathcal{A})=\{w\in\Sigma^{*}|\pi\in IP(A, w)$ thatconvergeson
$D_{m}$ at the m-th step, for
some
$m\geq|w|$, and$f\subseteq D_{m}$}.
Let $\mathcal{A}$be an RAand$f$ beafunctiondefined on
N. Motivated by the notion of
a
workspace fora phrase-structure grammar ([8]), we define: for
$w\in L(\mathcal{A})$ with$n=|w|$, and for$\pi$ in$IP(\mathcal{A}, w)$,
$WS(w, \pi)=\max_{i}$
{
$|D_{i}||D_{i}$ appearsin $\pi$}.
Further, the workspace
of
$\mathcal{A}$for
$w$ isdefined as:Example1. Let
us
considerareactionautomaton$\mathcal{A}=(S, \Sigma, A, D_{0}, f)$ defined asfollows:
$S=\{a,b, c, d, e, f\}$ with$\Sigma=\{a\}$, $A=\{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}\}$, where
$a_{1}=(a^{2}, \emptyset, b),$ $a_{2}=(b^{2}, ac,c),$ $a_{3}=(c^{2}, b, b)$,
$a_{4}=(bd,$$ac,$ $e),$ $a_{5}=(cd,$$b,$$e)$, 下6 $=(e,$$abc,$$f)$,
$D_{0}=d$
.
Let $w=$
aaaaaaaa
$\in S^{*}$ be the input string andconsider
an
interactive process$\pi$ such that$\pi$: $darrow^{a}adarrow^{a}bdarrow^{a}abdarrow^{a}b^{2}darrow^{a}ab^{2}d$
$arrow^{a}b^{3}darrow^{a}ab^{3}darrow^{a}b^{4}darrow c^{2}darrow bdarrow earrow f$.
It can be easily
seen
that $\pi\in IP(\mathcal{A}, w)$ and $w\in$$L(\mathcal{A})$
.
For instance,since $a_{2}^{2}\in En_{A}^{p}(b^{4}d)$, it holds$|$
that $c^{2}d\in{\rm Res}_{A}(b^{4}d)$
.
Hence, the step $b^{4}darrow c^{2}d$isvalid. We
can
alsosee
that$L(\mathcal{A})=\{a^{2}" |n\geq 1\}$whichis context-sensitive (seeFigure $1-(i)$).
$\}$
We shall show the equivalence of the accepting a
powers between reaction machines and Turingma- a
chines. For the details of proof,we refer [6]. $($
$\langle$
Theorem 1. Every recursively enumerable
lan-$r$
guage is acceptedby areaction automaton.
$($
1
4
Space Complexity
Classes
$r$
We
now
consider space complexity issues ofre-$($
action automata. That is, we introduce
some
$($
subclasses of reaction automata and investigate
$’)$
the relationships between classes of languages
ac-$($
cepted by those subclasses of automata and
lan-guage classes in the Chomsky hierarchy.
$WS(w,A)= \min_{\pi}\{WS(w, \pi)|\pi\in IP(A, w)$,
where$\pi$
converges.}.
Definition 6. (i). An
RA
$\mathcal{A}$is$f(n)$-boundedifforany$w\in L(\mathcal{A})$ with$n=|w|,$ $WS(w,A)$ is bounded
by$f(n)$.
(ii). If a function $f(n)$ is
a
constant $k$(lin-ear, polynomial, exponential), then $\mathcal{A}$ is
termed
k-bounded (resp. linearly-bounded,
polynomially-bounded,exponentially-bounded), and denotedby
k-RA (resp. lin-RA, poly-RA, exp-RA). Further,
the class of languages acceptedby k-RA (lin-RA,
poly-RA, exp-RA, arbitrary RA) is denotedby
k-$\mathcal{R}A$ $($resp. $\mathcal{L}\mathcal{R}\mathcal{A},\mathcal{P}\mathcal{R}\mathcal{A},\mathcal{E}\mathcal{R}A,\mathcal{R}\mathcal{A})$
.
Let
us
denote by $\mathcal{R}\mathcal{E}\mathcal{G}(\mathcal{L}\mathcal{I}\mathcal{N},C\mathcal{F},CS,\mathcal{R}\mathcal{E})$ theclassofregular (resp. linear, context-hee,
context-sens ’
$ve,$ recursvely enumerable)languages.
We show two characterizations concerning$\mathcal{L}\mathcal{R}\mathcal{A}$
and $\mathcal{E}\mathcal{R}\mathcal{A}$ in relation to the Chomsky hierarch.,
ndtwo interesting results. Oneis concerned with
representationtheorem forthe class$\mathcal{R}\mathcal{E}$ interms
of$\mathcal{L}\mathcal{R}\mathcal{A}$, and the other isa newcharacterization of $CS$with $\mathcal{E}\mathcal{R}\mathcal{A}$(for the proofs,
see
[7]).Theorem 2. For any recursively enumerable
lan-guage $L$, there exists
an
$LRA$ $A$ such that $L=$$h(L(\mathcal{A}))$
for
some
projection$h$.
Theorem 3. The followinginclusions hold:
(1). $CS=\mathcal{E}\mathcal{R}\mathcal{A}$
.
(2). $\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}$ (foreach$k\geq 1$).
(3). $\mathcal{L}\mathcal{I}\mathcal{N}(C\mathcal{F})$ and$\mathcal{L}\mathcal{R}\mathcal{A}$ are incomparable.
図 1: (i) Interactive processes for accepting $a^{2},$ $a^{4}$ and $a^{8}$ in $\mathcal{A}$
.
(ii) Language class relations in theChomsky hierarchy: $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\}^{*}\}$
.
5
Concluding Remarks
参考文献
[1] C. Calude, Gh. $P\dot{a}un$, G. Rozenberg and A.
Salomaa (Eds.), Multiset Processing, LNCS
2235, Springer,
2001.
[2] Gh. Paun,
G.
Rozenberg, A. Salomaa (Eds.),Handbook
of
Membrvnne Computing, OxfordUniversity Press, 2010.
[3] A. Ehrenfeucht, G. Rozenberg, Reaction
systems, Ibndamenta
Informaticae
vol.75,pp.263-280, 2007.
[4] A. Ehrenfeucht, G. Rozenberg, Events and
modules inreactionsystems,
Theoretical
Com-puterSciencevol.376, pp.3-16,
2007.
[5] A. Ehrenfeucht,
G.
Rozenberg, Introducingtime in reaction systems, Theoretical
Com-puterSciencevol.410, pp.310-322, 2009.
[6] F. Okubo, S. Kobayashi, T. Yokomori,
Reac-tion Automata, arXiv:1201.$3082v2$, to appear
inTheoretical ComputerScience.
[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, Academic
Press, New York, 1973.
[9] Y. Suzuki, Y. FMjiwara, J. Talabayashi, H.
Tanaka, AItificialLife Applications of
a
Classof P Systems, in: Multiset Processing, C.
Calude, Gh. $P\dot{a}$un, G. Rozenberg, A.
Salo-maa
(Eds.),LNCS2235,Springer, pp.299-346,2001.
