Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T03:25:05.596Z 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. [email protected]
Get access

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 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
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 1: Non-Classical Models of Automata and Applications (NCMA 2012) , January 2014 , pp. 23 - 38
Copyright
© EDP Sciences 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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 [email protected] 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