User:Dionysusbunny

{{UserboxCOI|1=cP systems}}

Introduction

cP systems (P systems with complex objects / symbols) are variants of membrane computing systems (p systems). cP systems share the fundamental features of traditional cell-like (tree-based) and tissue (graph-based) P systems. Top-level cells in cP systems construct a network of cells, and each top-level cell has its membrane structure, objects and rewriting rules.

A bird's eye view of a cP system

Top-level cells are represented as labelled nested multiset-based terms, and has its own evolution rules. Sub-cells are only used to represent local data. Evolution rules in cP systems are generic, which contain first-order variables.

History

cP systems are designed in 2013 by Romanian mathematician Radu Nicolescu (https://www.mathgenealogy.org/id.php?id=99039&fChrono=1), who worked in the University of Auckland from 1999 to 2021. A general introduction of cP systems can be found in . cP systems are successfully used for providing (theoretical) linear or sublinear solutions to several computationally hard problems, which include the Hamiltonian Cycle (HCP) and Travelling Salesman Problems (TSP), the subset sum problem, the general Sudoku problem, and a PSPACE-complete problem.

Term Grammar

Grammar of cP systems

The syntax of cP systems includes the definition of terms, states and rules. The basic vocabulary of cP systems is simple term, which consists of atom and variable. Lowercase letters are used to represent atoms and uppercase letters denote variables. For instance, a, b, c are atoms and X, Y, Z are variables. As a special atom, unity symbol 1 is used to represent unary numbers. For example, the natural number 1 is represented as 1, 2 is represented as 11 or 1², 3 is represented as 111 or 1³, and so on. Underscores (_) are used to denote anonymous variables. λ refers to the empty multiset.

Compound terms are recursively built by terms (multisets) with functors, where functors are atoms. For example, f(1), a(b), a(b(cX)d(e_)) are compound terms. Compound terms are often used to represent cells, for instance, a cell with label a contains two atoms b and c can be presented as a(bc). Compound terms are multiset-based, the writing order of their contents does not matter. For example, a(bbc) and a(cbb) are identical, both of them represent a cell (multiset) labelled as a, which contains three atoms b, b and c. For readability, commas (,) and blank spaces can be used in compound terms as delimiters, without changing terms' values. For example, a(bc), a(b c) and a(b; c) are identical.

Rule Grammar

Top-level cells in cP systems have evolution rules. A rule consists of lhs, rhs, promoters and application model α. Both a rule's lhs and rhs contain a state and a multiset of terms.

For example: s₁ a →₁ s₂ bc is a rewriting rule, whose l-state is s₁, r-state is s₂. Atom a is a terms in its lhs, atoms b and c are terms in its rhs. This rule consumes a term a and produces two terms b and c (it rewrites a as bc).

Each cP system (top-level cell) contains a number of terms alternatively named system terms, and has a state named system state. States are atoms, to distinguish them with terms, it is conventional to write them as atom s with subscripts of numbers, for example: s₁, s₂ and s₃.

A rule is applicable if and only if its l-state matches the system state, and its lhs terms and promoters can be found in the system. After applying it, terms match its lhs will be consumed, terms match its rhs will be produced, and the system state will be changed to the rule's r-state. In membrane computing, if a rule is applicable, it must apply.

Pattern Matching

For generic rules with variable terms such as a(X), b(_), cP systems support a one-way unification (pattern matching). After successfully unifying a rule's variable terms against systems terms, it can be applied. Suppose a cP system (at state s1) that has two terms a(1), a(11) and a generic rule s1 a(X) →₁ s2 b(X). The rule's lhs variable term a(X) will be unified against system terms a(1) and a(11). Two unifiers can be found here, which are θ₁ = {X → 1} (mapsto) and θ₂ = {X → 11}. Since the application model of this rule is "exactly-once", it will only apply once. cP systems are nondeterministic, thus one of θ₁ and θ₂ will be randomly selected. Suppose θ₁ is selected, the rule will transform into a ground rule (ground means "without variables") s1 a(1) →₁ s2 b(1); then the system will apply it, consume a(1) and produce b(1).

Application Model

Two major application models are supported in cP systems, which are "exactly-once (1)" and "max-parallel (+)". In the exactly-once model, a rule will only apply once. In the max-parallel model, a rule will apply to all possible terms simultaneously.

For example, suppose a cP system at s₁ contains two terms a(1) and a(11), by applying the rule s1 a(X) →₁ s2 b(X), one of a(1) and a(11) will be randomly selected and consumed, and the correspondence product b(1) or b(11) will be produced. The computation result of the system can be a(1) b(11) or a(11) b(1). If the rule is max-parallel, i.e. s1 a(X) →₊ s2 b(X), both a(1) and a(11) will be consumed, and the computation result will be b(1) b(11).

System Efficiency

Similar to other P system variants, cP systems are much efficient than traditional Turing complete models, by accepting the hypothesis with unlimited computational power and memory space.