Reaction automata working in sequential manner

Fumiya Okubo

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

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

Abstract

top
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.

How to cite

top

Okubo, 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. [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. [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. [3] E. Csuhaj-Varjú, M. Oswald and Gy. Vaszil, P automata, in The Oxford Handbook of Membrane Computing (2010) 145–167. 
  4. [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. [5] A. Ehrenfeucht and G. Rozenberg, Reaction systems. Fund. Inform.75 (2007) 263–280. Zbl1108.68056MR2293699
  6. [6] A. Ehrenfeucht and G. Rozenberg, Events and modules in reaction systems. Theoret. Comput. Sci.376 (2007) 3–16. Zbl1119.93011MR2316386
  7. [7] A. Ehrenfeucht and G. Rozenberg, Introducing time in reaction systems. Theoret. Comput. Sci.410 (2009) 310–322. Zbl1156.93306MR2493981
  8. [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. [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. [10] P.C. Fischer, Turing Machines with Restricted Memory Access. Inform. Control9 (1966) 364–379. Zbl0145.24205MR199061
  11. [11] M. Hirvensalo, On probabilistic and quantum reaction systems. Theoret. Comput. Sci.429 (2012) 134–143. Zbl1248.68197MR2901403
  12. [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. [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. [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. [15] F. Okubo, S. Kobayashi and T. Yokomori, Reaction Automata. Theoret. Comput. Sci.429 (2012) 247–257. Zbl1276.68074MR2901416
  16. [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. [17] A. Salomaa, Formal Languages. Academic Press, New York (1973). Zbl0686.68003MR438755
  18. [18] A. Salomaa, Functions and sequences generated by reaction systems. Theoret. Comput. Sci.466 (2012) 87–96. Zbl1321.68268MR2997425

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.