P systems with deadlock.
Rewriting P systems with parallel application of evolution rules, as defined in Besozzi et al. [Parallel rewriting P systems with deadlock. In: Hagiya, M., Ohuchi, A. (Eds.), Pre-Proceedings of DNA8 Conference, Hokkaido University, Japan, June 2002a, pp. 171-183], are considered here. Different kinds of parallelism methods are defined for string rewriting. The notion of deadlock is then introduced to describe situations where rules with mixed target indications are simultaneously applied to a common string. The generative power of parallel P systems with deadlock is analyzed, with respect to Lindenmayer systems, and some relations among different types of parallel P systems with or without deadlock, allowing to rewrite all occurrences of a single symbol, or all the symbols applying either any of the rules or only those belonging to a specific set (table) of rules are studied. Some open problems are also formulated.
Besozzi
Daniela
D
Dipartimento di Scienze Chimiche, Università degli Studi dell'Insubria Fisiche e Matematiche, Via Valleggio 11, 22100 Como, Italy. daniela.besozzi@uninsubria.it
Ferretti
Claudio
C
Mauri
Giancarlo
G
Zandron
Claudio
C
D000465:Algorithms; D001683:Biological Clocks / Q000502:physiology*; D002450:Cell Communication / Q000502:physiology*; D002462:Cell Membrane / Q000502:physiology*; D002468:Cell Physiological Phenomena; D039301:Computers, Molecular; D004777:Environment; D005110:Extracellular Space / Q000502:physiology*; D008954:Models, Biological; D017711:Nonlinear Dynamics; D010507:Periodicity; D009626:Terminology as Topic