Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2014__48_1_23_0,
author = {Okubo, Fumiya},
title = {Reaction automata working in sequential manner},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {23--38},
publisher = {EDP-Sciences},
volume = {48},
number = {1},
year = {2014},
doi = {10.1051/ita/2013047},
mrnumber = {3195787},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2013047/}
}
TY - JOUR AU - Okubo, Fumiya TI - Reaction automata working in sequential manner JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2014 SP - 23 EP - 38 VL - 48 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2013047/ DO - 10.1051/ita/2013047 LA - en ID - ITA_2014__48_1_23_0 ER -
%0 Journal Article %A Okubo, Fumiya %T Reaction automata working in sequential manner %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 23-38 %V 48 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2013047/ %R 10.1051/ita/2013047 %G en %F ITA_2014__48_1_23_0
Okubo, Fumiya. Reaction automata working in sequential manner. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 23-38. doi: 10.1051/ita/2013047
Cité par Sources :