In parallel rewriting P systems, the notion of deadlock is used to describe situations where evolution rules with different target indications are simultaneously applied on a common string. In this paper we claim that the generative power of partial parallel P systems (PPP, in short) with deadlock is equivalent to matrix grammars without appearance checking, and we prove that it is decidable whether or not a PPP will ever reach a deadlock configuration. Work partially supported by contribution of EU commission under The Fifth Framework Programme, project ”MolCoNet” IST-2001-32008. This revised version was published in November 2004 and replaces the previous preliminary version.
Besozzi, D., Mauri, G., Zandron, C. (2004). Deadlock Decidability in Partial Parallel P Systems. In DNA Computing: 9th International Meeting on DNA-Based Computers (pp.55-60). Springer-Verlag [10.1007/978-3-540-24628-2_7].
Deadlock Decidability in Partial Parallel P Systems
BESOZZI, DANIELA;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2004
Abstract
In parallel rewriting P systems, the notion of deadlock is used to describe situations where evolution rules with different target indications are simultaneously applied on a common string. In this paper we claim that the generative power of partial parallel P systems (PPP, in short) with deadlock is equivalent to matrix grammars without appearance checking, and we prove that it is decidable whether or not a PPP will ever reach a deadlock configuration. Work partially supported by contribution of EU commission under The Fifth Framework Programme, project ”MolCoNet” IST-2001-32008. This revised version was published in November 2004 and replaces the previous preliminary version.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
