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. BesozziPrimo
;
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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
