Okubo, F. (2014). Reaction automata working in sequential manner∗∗∗. RAIRO-Theoretical Informatics and Applications, 48(1), 23-38.
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.
Okubo, F. (2014). Reaction automata working in sequential manner∗∗∗. RAIRO-Theoretical Informatics and Applications, 48(1), 23-38.
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.
Link to the online copy
Bibtex file @article{okubo2014reaction, title={Reaction automata working in sequential manner∗∗∗}, author={Okubo, Fumiya}, journal={RAIRO-Theoretical Informatics and Applications}, volume={48}, number={1}, pages={23--38}, year={2014}, publisher={EDP Sciences} }