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.