Reaction automata working in sequential manner
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 23-38.

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.

DOI : 10.1051/ita/2013047
Classification : 68Q05, 68Q45
Mots-clés : models of biochemical reactions, sequential reaction automata, space complexity, Turing machines 
@article{ITA_2014__48_1_23_0,
     author = {Okubo, Fumiya},
     title = {Reaction automata working in sequential manner},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {23--38},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {1},
     year = {2014},
     doi = {10.1051/ita/2013047},
     mrnumber = {3195787},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2013047/}
}
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
SP  - 23
EP  - 38
VL  - 48
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2013047/
DO  - 10.1051/ita/2013047
LA  - en
ID  - ITA_2014__48_1_23_0
ER  - 
%0 Journal Article
%A Okubo, Fumiya
%T Reaction automata working in sequential manner
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2014
%P 23-38
%V 48
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2013047/
%R 10.1051/ita/2013047
%G en
%F ITA_2014__48_1_23_0
Okubo, Fumiya. Reaction automata working in sequential manner. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 23-38. doi : 10.1051/ita/2013047. http://www.numdam.org/articles/10.1051/ita/2013047/

[1] C. Calude, Gh. Păun, G. Rozenberg and A. Salomaa, Multiset Processing. In vol. 2235 of Lect. Notes Comput. Sci. Springer (2001). | MR | Zbl

[2] E. Csuhaj-Varjú, O.H. Ibarra and Gy. Vaszil, On the computational complexity of P automata. Nat. Comput. 5 (2006) 109-126. | MR | Zbl

[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. | MR | Zbl

[5] A. Ehrenfeucht and G. Rozenberg, Reaction systems. Fund. Inform. 75 (2007) 263-280. | MR | Zbl

[6] A. Ehrenfeucht and G. Rozenberg, Events and modules in reaction systems. Theoret. Comput. Sci. 376 (2007) 3-16. | MR | Zbl

[7] A. Ehrenfeucht and G. Rozenberg, Introducing time in reaction systems. Theoret. Comput. Sci. 410 (2009) 310-322. | MR | Zbl

[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. | MR | Zbl

[9] A. Ehrenfeucht, M. Main and G. Rozenberg, Functions defined by reaction systems. Int. J. Found. Comput. Sci. 22 (2011) 167-178. | MR | Zbl

[10] P.C. Fischer, Turing Machines with Restricted Memory Access. Inform. Control 9 (1966) 364-379. | MR | Zbl

[11] M. Hirvensalo, On probabilistic and quantum reaction systems. Theoret. Comput. Sci. 429 (2012) 134-143. | MR | Zbl

[12] J.E. Hopcroft, T. Motwani and J.D. Ullman, Introduction to automata theory, language and computation, 2nd edition. Addison-Wesley (2003). | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[17] A. Salomaa, Formal Languages. Academic Press, New York (1973). | MR | Zbl

[18] A. Salomaa, Functions and sequences generated by reaction systems. Theoret. Comput. Sci. 466 (2012) 87-96. | MR

Cité par Sources :