Rewriting P systems with parallel application of evolution rules are considered here. Different kinds of parallelism methods are defined for string rewriting. The notion of deadlock is then introduced to describe situations where rules with mixed target indications are simultaneously applied to a common string. The generative power of parallel P systems with deadlock is analyzed, with respect to Lindenmayer systems, and some relations among different types of parallel P systems with or without deadlock, allowing to rewrite all occurrences of a single symbol, or all the symbols applying either any of the rules or only those belonging to a specific set (table) of rules are studied. Some open problems are also formulated.
Besozzi, D., Ferretti, C., Mauri, G., Zandron, C. (2003). P systems with deadlock. BIOSYSTEMS, 70(2), 95-105 [10.1016/S0303-2647(03)00033-9].
P systems with deadlock
BESOZZI, DANIELA;FERRETTI, CLAUDIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2003
Abstract
Rewriting P systems with parallel application of evolution rules are considered here. Different kinds of parallelism methods are defined for string rewriting. The notion of deadlock is then introduced to describe situations where rules with mixed target indications are simultaneously applied to a common string. The generative power of parallel P systems with deadlock is analyzed, with respect to Lindenmayer systems, and some relations among different types of parallel P systems with or without deadlock, allowing to rewrite all occurrences of a single symbol, or all the symbols applying either any of the rules or only those belonging to a specific set (table) of rules are studied. Some open problems are also formulated.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
