We analyze P systems with different parallel methods for string rewriting. The notion of deadlock state is introduced when some rules with mixed target indications are simultaneously applied on a common string. The computational power of systems with and without deadlock is analyzed and a lower bound for the generative power is given, for some parallelism methods. Some open problems are also formulated.
Parallel rewriting P systems with deadlock / D. Besozzi, C. Ferretti, G. Mauri, C. Zandron - In: DNA Computing : 8th International Workshop on DNA Based Computers, DNA8 : Sapporo, Japan, June 10-13, 2002 : Revised Papers / M. Hagiya, A. Ohuchi. - Berlin : Springer-Verlag, 2003. - ISBN 3540005315. - pp. 302-314 (( Intervento presentato al 8. convegno International Workshop on DNA Based Computers tenutosi a Sapporo, Japan nel 2002.
Parallel rewriting P systems with deadlock
D. BesozziPrimo
;
2003
Abstract
We analyze P systems with different parallel methods for string rewriting. The notion of deadlock state is introduced when some rules with mixed target indications are simultaneously applied on a common string. The computational power of systems with and without deadlock is analyzed and a lower bound for the generative power is given, for some parallelism methods. Some open problems are also formulated.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
