×

Reaction automata working in sequential manner. (English) Zbl 1366.68062

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.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Numdam