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.
No
slide + paper
Scientifica
deadlock decidability, P systems, membrane systems, natural computing
English
International Workshop on DNA Based Computers
9783540209300
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].
Besozzi, D; Mauri, G; Zandron, C
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10281/16112
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
Social impact