Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T23:52:49.668Z Has data issue: false hasContentIssue false
  • English
  • Français

Reaction automata working in sequential manner∗∗∗

Published online by Cambridge University Press:  21 January 2014

Fumiya Okubo
Fumiya Okubo*
Affiliation:
Graduate School of Education, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan. f.okubo@akane.waseda.jp

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 rewritingmechanism. In this paper, we continue the investigation of RAs with a focus on the twomanners of rule application: maximally parallel and sequential. Considering restrictionson the workspace and the λ-input mode, we introduce the correspondingvariants of RAs and investigate their computation powers. In order to explore Turingmachines (TMs) that correspond to RAs, we also introduce a new variant of TMs withrestricted workspace, called s(n)-restricted TMs. Themain results include the following: (i) for a language L and a functions(n), L is accepted by ans(n)-bounded RA with λ-input mode insequential manner if and only if L is accepted by alog s(n)-bounded one-way TM; (ii) if a languageL is accepted by a linear-bounded RA in sequential manner, thenL is also accepted by a P automaton [Csuhaj−Varju and Vaszil, vol. 2597of Lect. Notes Comput. Sci. Springer (2003) 219–233.] in sequentialmanner; (iii) the class of languages accepted by linear-bounded RAs in maximally parallelmanner is incomparable to the class of languages accepted by RAs in sequential manner.

Keywords

Models of biochemical reactionssequential reaction automataspace complexityTuring machines

References

C. Calude, Gh. Păun, G. Rozenberg and A. Salomaa, Multiset Processing. In vol. 2235 of Lect. Notes Comput. Sci. Springer (2001).
Csuhaj-Varjú, E., Ibarra, O.H. and Vaszil, Gy., On the computational complexity of P automata. Nat. Comput. 5 (2006) 109–126. Google Scholar
E. Csuhaj-Varjú, M. Oswald and Gy. Vaszil, P automata, in The Oxford Handbook of Membrane Computing (2010) 145–167.
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.
Ehrenfeucht, A. and Rozenberg, G., Reaction systems. Fund. Inform. 75 (2007) 263–280. Google Scholar
Ehrenfeucht, A. and Rozenberg, G., Events and modules in reaction systems. Theoret. Comput. Sci. 376 (2007) 3–16. Google Scholar
Ehrenfeucht, A. and Rozenberg, G., Introducing time in reaction systems. Theoret. Comput. Sci. 410 (2009) 310–322. Google Scholar
Ehrenfeucht, A., Main, M. and Rozenberg, G., Combinatorics of life and death in reaction systems. Int. J. Found. Comput. Sci. 21 (2010) 345–356. Google Scholar
Ehrenfeucht, A., Main, M. and Rozenberg, G., Functions defined by reaction systems. Int. J. Found. Comput. Sci. 22 (2011) 167–178. Google Scholar
Fischer, P.C., Turing Machines with Restricted Memory Access. Inform. Control 9 (1966) 364–379. Google Scholar
Hirvensalo, M., On probabilistic and quantum reaction systems. Theoret. Comput. Sci. 429 (2012) 134–143. Google Scholar
J.E. Hopcroft, T. Motwani and J.D. Ullman, Introduction to automata theory, language and computation, 2nd edition. Addison-Wesley (2003).
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.
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.
Okubo, F., Kobayashi, S. and Yokomori, T., Reaction Automata. Theoret. Comput. Sci. 429 (2012) 247–257. Google Scholar
Okubo, F., Kobayashi, S. and Yokomori, T., On the Properties of Language Classes Defined by Bounded Reaction Automata. Theoret. Comput. Sci. 454 (2012) 206–221. Google Scholar
A. Salomaa, Formal Languages. Academic Press, New York (1973).
Salomaa, A., Functions and sequences generated by reaction systems. Theoret. Comput. Sci. 466 (2012) 87–96. Google Scholar