We consider parallel rewriting P systems with deadlock, that is P systems with string objects in which rules are applied in parallel on the symbols of the string; when two or more rules with different target indications are simultaneously applied to a common string, we say that the string is in a deadlock condition and it cannot further evolve, hence it can not contribute to the output of the system. In this paper we analyze parallel rewriting P systems with deadlock, we compare them to Lindenmayer systems and matrix grammars and consider the use of different parallel rewriting methods. The issue of deadlock decidability is also addressed. We conclude by suggesting some problems still open to the future research.
Besozzi, D., Mauri, G., Zandron, C. (2004). A survey of latest results on P System with deadlock. In M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini (a cura di), Recent Results in Natural Computing (pp. 17-46). Sevilla : Fénix Editora.
A survey of latest results on P System with deadlock
BESOZZI, DANIELA;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2004
Abstract
We consider parallel rewriting P systems with deadlock, that is P systems with string objects in which rules are applied in parallel on the symbols of the string; when two or more rules with different target indications are simultaneously applied to a common string, we say that the string is in a deadlock condition and it cannot further evolve, hence it can not contribute to the output of the system. In this paper we analyze parallel rewriting P systems with deadlock, we compare them to Lindenmayer systems and matrix grammars and consider the use of different parallel rewriting methods. The issue of deadlock decidability is also addressed. We conclude by suggesting some problems still open to the future research.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.