On maximal parallel application of rules in rewriting P systems

被引:1
作者
Zandron, Claudio [1 ]
机构
[1] Univ Milano Bicocca, Dipartimento Informat Sistemist & Comunicaz, Viale Sarca 336, I-20126 Milan, Italy
关键词
Membrane computing; Parallel rewriting; Lindenmayer system; Matrix grammars; Chomsky grammars; ACTIVE MEMBRANES; COMPLEXITY; HIERARCHIES;
D O I
10.1007/s41965-023-00127-8
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In rewriting P systems, that is P systems using structured strings instead of atomic symbols, rules can be applied in parallel on all strings, but a single rule at a time can be applied on each string. Nonetheless, parallel application of rules also on each string has been considered in various works. This leads to possible application of rules with conflicting target indications on the same string, and different strategies have been considered to face this problem; relations among different classes of languages generated in this way have been investigated in the literature. We continue the investigation on this subject, by highlighting some relations among different classes of maximally parallel rewriting P systems by means of direct simulations. The advantages of such simulations are highlighted, by showing how theoretical results concerning one such type of systems can immediately be adapted to the corresponding simulating systems.
引用
收藏
页码:170 / 181
页数:12
相关论文
共 61 条
[1]   Evaluating space measures in P systems [J].
Alhazov, Artiom ;
Leporati, Alberto ;
Manzoni, Luca ;
Mauri, Giancarlo ;
Zandron, Claudio .
JOURNAL OF MEMBRANE COMPUTING, 2022, 4 (03) :251-260
[2]   When catalytic P systems with one catalyst can be computationally complete [J].
Alhazov, Artiom ;
Freund, Rudolf ;
Ivanov, Sergiu .
JOURNAL OF MEMBRANE COMPUTING, 2021, 3 (03) :170-181
[3]   Alternative space definitions for P systems with active membranes [J].
Alhazov, Artiom ;
Leporati, Alberto ;
Manzoni, Luca ;
Mauri, Giancarlo ;
Zandron, Claudio .
JOURNAL OF MEMBRANE COMPUTING, 2021, 3 (02) :87-96
[4]   Space complexity equivalence of P systems with active membranes and Turing machines [J].
Alhazov, Artiom ;
Leporati, Alberto ;
Mauri, Giancarlo ;
Porreca, Antonio E. ;
Zandron, Claudio .
THEORETICAL COMPUTER SCIENCE, 2014, 529 :69-81
[5]   P systems in the time of COVID-19 [J].
Baquero, Fernando ;
Campos, Marcelino ;
Llorens, Carlos ;
Sempere, Jose M. .
JOURNAL OF MEMBRANE COMPUTING, 2021, 3 (04) :246-257
[6]   Hierarchies of parallel rewriting P systems - A survey [J].
Besozzi, D ;
Mauri, G ;
Zandron, C .
NEW GENERATION COMPUTING, 2004, 22 (04) :331-347
[7]  
Besozzi D, 2004, LECT NOTES COMPUT SC, V2933, P55
[8]  
Besozzi D, 2003, LECT NOTES COMPUT SC, V2597, P119
[9]  
Besozzi D, 2003, LECT NOTES COMPUT SC, V2568, P302
[10]   P systems with deadlock [J].
Besozzi, D ;
Ferretti, C ;
Mauri, G ;
Zandron, C .
BIOSYSTEMS, 2003, 70 (02) :95-105