Nicolescu, Radu, and Henderson, Alec (2018) An introduction to cP systems. In: Graciani, Carmen, Paun, Gheorghe, Rozenberg, Grzegorz, Salomaa, Arto, and Riscos Núñez, Agustín, (eds.) Enjoying Natural Computing Essays Dedicated to Mario de Jesus Perez-Jimenez on the Occasion of His 70th Birthday. Lecture Notes in Computer Science, 11270 . Springer, Cham, Switzerland, pp. 204-227.

PDF (Published Version) - Published Version Restricted to Repository staff only

11

Abstract

We overview the current state of cP systems and illustrate it with a series of old and new examples, intentionally simple, but fundamental in their areas. cP systems – i.e. P systems with compound terms – share the fundamental features of traditional cell-like (tree-based) and tissue (graph-based) P systems: unlimited space and computing power, cells, nested cells, multisets, messages, rewriting rules, possibly running in maximal parallel modes. In contrast to traditional P systems, inner nested cells do not have their own rulesets. However, this restriction is usually more than compensated by their significant extensions: compound Prolog-like terms, high-level rules, control on incoming messages. Additionally, the same rulesets can run in either synchronous or asynchronous mode, without any syntactic change. cP systems have been successfully used to model quite a few fundamental and real-life problems, e.g. in NP complexity, data structures, graph theory, distributed algorithms, image processing. As trademark, cP models use fixed sized alphabets and crisp rulesets, independent of the problem size. The samples cover a wide variety of areas, such as arithmetic, list structures, summary statistics and sorting, asynchronous communications, μ -recursive functions.

Actions (Repository Staff Only)

Item Control Page