# Reaction automata working in sequential manner

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 1, page 23-38
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topOkubo, Fumiya. "Reaction automata working in sequential manner." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.1 (2014): 23-38. <http://eudml.org/doc/273029>.

@article{Okubo2014,

abstract = {Based on the formal framework of reaction systems by Ehrenfeucht and Rozenberg [Fund. Inform. 75 (2007) 263–280], reaction automata (RAs) have been introduced by Okubo et al. [Theoret. Comput. Sci. 429 (2012) 247–257], as language acceptors with multiset rewriting mechanism. In this paper, we continue the investigation of RAs with a focus on the two manners of rule application: maximally parallel and sequential. Considering restrictions on the workspace and the λ-input mode, we introduce the corresponding variants of RAs and investigate their computation powers. In order to explore Turing machines (TMs) that correspond to RAs, we also introduce a new variant of TMs with restricted workspace, called s(n)-restricted TMs. The main results include the following: (i) for a language L and a function s(n), L is accepted by an s(n)-bounded RA with λ-input mode in sequential manner if and only if L is accepted by a log s(n)-bounded one-way TM; (ii) if a language L is accepted by a linear-bounded RA in sequential manner, then L is also accepted by a P automaton [Csuhaj−Varju and Vaszil, vol. 2597 of Lect. Notes Comput. Sci. Springer (2003) 219–233.] in sequential manner; (iii) the class of languages accepted by linear-bounded RAs in maximally parallel manner is incomparable to the class of languages accepted by RAs in sequential manner.},

author = {Okubo, Fumiya},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {models of biochemical reactions; sequential reaction automata; space complexity; Turing machines},

language = {eng},

number = {1},

pages = {23-38},

publisher = {EDP-Sciences},

title = {Reaction automata working in sequential manner},

url = {http://eudml.org/doc/273029},

volume = {48},

year = {2014},

}

TY - JOUR

AU - Okubo, Fumiya

TI - Reaction automata working in sequential manner

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2014

PB - EDP-Sciences

VL - 48

IS - 1

SP - 23

EP - 38

AB - Based on the formal framework of reaction systems by Ehrenfeucht and Rozenberg [Fund. Inform. 75 (2007) 263–280], reaction automata (RAs) have been introduced by Okubo et al. [Theoret. Comput. Sci. 429 (2012) 247–257], as language acceptors with multiset rewriting mechanism. In this paper, we continue the investigation of RAs with a focus on the two manners of rule application: maximally parallel and sequential. Considering restrictions on the workspace and the λ-input mode, we introduce the corresponding variants of RAs and investigate their computation powers. In order to explore Turing machines (TMs) that correspond to RAs, we also introduce a new variant of TMs with restricted workspace, called s(n)-restricted TMs. The main results include the following: (i) for a language L and a function s(n), L is accepted by an s(n)-bounded RA with λ-input mode in sequential manner if and only if L is accepted by a log s(n)-bounded one-way TM; (ii) if a language L is accepted by a linear-bounded RA in sequential manner, then L is also accepted by a P automaton [Csuhaj−Varju and Vaszil, vol. 2597 of Lect. Notes Comput. Sci. Springer (2003) 219–233.] in sequential manner; (iii) the class of languages accepted by linear-bounded RAs in maximally parallel manner is incomparable to the class of languages accepted by RAs in sequential manner.

LA - eng

KW - models of biochemical reactions; sequential reaction automata; space complexity; Turing machines

UR - http://eudml.org/doc/273029

ER -

## References

top- [1] C. Calude, Gh. Păun, G. Rozenberg and A. Salomaa, Multiset Processing. In vol. 2235 of Lect. Notes Comput. Sci. Springer (2001). Zbl0983.00053MR2054251
- [2] E. Csuhaj-Varjú, O.H. Ibarra and Gy. Vaszil, On the computational complexity of P automata. Nat. Comput. 5 (2006) 109–126. Zbl1112.68057MR2259031
- [3] E. Csuhaj-Varjú, M. Oswald and Gy. Vaszil, P automata, in The Oxford Handbook of Membrane Computing (2010) 145–167.
- [4] E. Csuhaj-Varjú and Gy. Vaszil, P automata or purely communicating accepting P systems. In vol. 2597 of Lect. Notes Comput. Sci. Springer (2003) 219–233. Zbl1023.68039MR2048885
- [5] A. Ehrenfeucht and G. Rozenberg, Reaction systems. Fund. Inform.75 (2007) 263–280. Zbl1108.68056MR2293699
- [6] A. Ehrenfeucht and G. Rozenberg, Events and modules in reaction systems. Theoret. Comput. Sci.376 (2007) 3–16. Zbl1119.93011MR2316386
- [7] A. Ehrenfeucht and G. Rozenberg, Introducing time in reaction systems. Theoret. Comput. Sci.410 (2009) 310–322. Zbl1156.93306MR2493981
- [8] A. Ehrenfeucht, M. Main and G. Rozenberg, Combinatorics of life and death in reaction systems. Int. J. Found. Comput. Sci.21 (2010) 345–356. Zbl1192.68458MR2653855
- [9] A. Ehrenfeucht, M. Main and G. Rozenberg, Functions defined by reaction systems. Int. J. Found. Comput. Sci.22 (2011) 167–178. Zbl1213.68259MR2764626
- [10] P.C. Fischer, Turing Machines with Restricted Memory Access. Inform. Control9 (1966) 364–379. Zbl0145.24205MR199061
- [11] M. Hirvensalo, On probabilistic and quantum reaction systems. Theoret. Comput. Sci.429 (2012) 134–143. Zbl1248.68197MR2901403
- [12] J.E. Hopcroft, T. Motwani and J.D. Ullman, Introduction to automata theory, language and computation, 2nd edition. Addison-Wesley (2003). Zbl0980.68066MR645539
- [13] M. Kudlek, C. Martin-Vide and Gh. Păun, Toward a formal macroset theory, in Multiset Processing, vol. 2235 of Lect. Notes Comput. Sci., edited by C. Calude, Gh. Păun, G. Rozenberg and A. Salomaa. Springer (2001) 123–134. Zbl1052.68063MR2054257
- [14] F. Okubo, On the Computational Power of Reaction Automata Working in Sequential Manner, in Proc. of 4th Workshop on Non-Classical Models for Automata and Applications, vol. 290 of book@ocg.at series. Öesterreichische Comput. Gesellschaft (2012) 149–164.
- [15] F. Okubo, S. Kobayashi and T. Yokomori, Reaction Automata. Theoret. Comput. Sci.429 (2012) 247–257. Zbl1276.68074MR2901416
- [16] F. Okubo, S. Kobayashi and T. Yokomori, On the Properties of Language Classes Defined by Bounded Reaction Automata. Theoret. Comput. Sci.454 (2012) 206–221. Zbl1252.68180MR2966636
- [17] A. Salomaa, Formal Languages. Academic Press, New York (1973). Zbl0686.68003MR438755
- [18] A. Salomaa, Functions and sequences generated by reaction systems. Theoret. Comput. Sci.466 (2012) 87–96. Zbl1321.68268MR2997425

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.