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.

Deadlock decidability in partial parallel P systems / D. Besozzi, G. Mauri, C. Zandron - In: DNA Computing: 9th International Workshop on DNA Based Computers, DNA9 : Madison, WI, USA, June 1-3, 2003 : Revised Papers / J. Chen, J. Reif. - Berlin : Springer-Verlag, 2004. - ISBN 3540209301. - pp. 55-60 (( Intervento presentato al 9. convegno International Workshop on DNA Based Computers tenutosi a Madison, WI, USA nel 2003.

Deadlock decidability in partial parallel P systems

D. Besozzi
Primo
;
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.
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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/2434/9964
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact