Okubo, Fumiya Reaction automata working in sequential manner. (English) Zbl 1366.68062 RAIRO, Theor. Inform. Appl. 48, No. 1, 23-38 (2014). Summary: Based on the formal framework of reaction systems by A. Ehrenfeucht and G. Rozenberg [Fundam. Inform. 75, No. 1–4, 263–280 (2007; Zbl 1108.68056)], reaction automata (RAs) have been introduced by the author et al. [Theor. Comput. Sci. 429, 247–257 (2012; Zbl 1276.68074)], 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 \(\lambda\)-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 \(\lambda\)-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 [E. Csuhaj-Varjú and G. Vaszil, Lect. Notes Comput. Sci. 2597, 219–233 (2003; Zbl 1023.68039)] 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. Cited in 1 ReviewCited in 4 Documents MSC: 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q45 Formal languages and automata Keywords:models of biochemical reactions; sequential reaction automata; space complexity; Turing machines Citations:Zbl 1108.68056; Zbl 1276.68074; Zbl 1023.68039 PDFBibTeX XMLCite \textit{F. Okubo}, RAIRO, Theor. Inform. Appl. 48, No. 1, 23--38 (2014; Zbl 1366.68062) Full Text: DOI Numdam