An introduction to cP systems

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 Jesús Pérez-Jiménez on the Occasion of His 70th Birthday. Lecture Notes in Computer Science, 11270 . Springer, Cham, Switzerland, pp. 204-227.

[img] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website:


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.

Item ID: 75514
Item Type: Book Chapter (Research - B1)
ISBN: 978-3-030-00264-0
Copyright Information: © Springer Nature Switzerland AG 2018
Date Deposited: 19 Jul 2022 23:21
FoR Codes: 46 INFORMATION AND COMPUTING SCIENCES > 4613 Theory of computation > 461399 Theory of computation not elsewhere classified @ 100%
SEO Codes: 28 EXPANDING KNOWLEDGE > 2801 Expanding knowledge > 280115 Expanding knowledge in the information and computing sciences @ 100%
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page