Many membrane systems (e.g. P System), including cP systems (P Systems with compound terms), have been used to solve efficiently many NP-hard problems, often in linear time. However, these solutions have been independent of each other and have not utilised the theory of reductions. This work presents a sublinear solution to k-SAT and demonstrates that k-colouring can be reduced to k-SAT in constant time. This work demonstrates that traditional reductions are efficient in cP systems and that they can sometimes produce more efficient solutions than the previous problem-specific solutions.

As a newly proposed computational paradigm of membrane computing, cP systems are used to solve several NP-complete and PSPACE-complete problems in linear or sub-linear time theoretically. Most cP systems proposed in previous studies lack of automated verification support. In this paper, we present cPV, the first software implementation for cP system simulation and verification. cPV offers multiple features, which include modelling, simulation, automated verification of properties such as absence of deadlock, confluence, termination, determinism, and goal reachability. As an extensible framework, modules in cPV are loosely coupled, where new verification algorithms, reduction techniques, and property specifications can be easily extended. To evaluate cPV, we constructed two benchmark datasets that cover several important aspects of cP systems. The experimental results demonstrated effective automatic verification support to the membrane computing problem domain.

The Hamiltonian Cycle Problem (HCP) and Travelling Salesman Problem (TSP) are long-standing and well-known NP-hard problems. The HCP is concerned with finding paths through a given graph such that those paths visit each node exactly once after the start, and end where they began (i.e., Hamiltonian cycles). The TSP builds on the HCP and is concerned with computing the lowest cost Hamiltonian cycle on a weighted (di)graph. Many solutions to these problems exist, including some from the perspective of P systems. For the TSP however, almost all these papers have combined membrane computing with other approaches for approximate solution algorithms, which is surprising given the plethora of P systems solutions to the HCP. A recent paper presented a brute-force style P systems solution to the TSP with a time complexity of O(n2), exploiting the ability of P systems to reduce time complexity in exchange for space complexity, but the resultant system had a fairly high number of rules, around 50. Inspired by this paper, and seeking a more concise representation of an exact brute-force TSP algorithm, we have devised a P systems algorithm based on cP systems (P systems with Complex Objects) which requires five rules and takes n + 3 steps. We first provide some background on cP systems and demonstrate a fast new cP systems method to find the minimum of a multiset, then describe our solution to the HCP, and build on that for our TSP algorithm. This paper describes said algorithms, and provides an example application of our TSP algorithm to a given graph and a digraph variant.

We propose a novel approach to justify and guide regularisation of an ill-posed one-dimensional global optimisation with multiple solutions using a massively parallel (P system) model of the solution space. Classical optimisation assumes a well-posed problem with a stable unique solution. Most of important practical problems are ill posed due to an unstable or non-unique global optimum and are regularised to get a unique best-suited solution. Whilst regularisation theory exists largely for unstable unique solutions, its recommendations are often routinely applied to inverse optical problems with essentially non-unique solutions, e.g. computer stereo vision or image segmentation, typically formulated in terms of global energy minimisation. In these cases the recommended regularisation becomes purely heuristic and does not guarantee a unique solution. As a result, classical optimisation algorithms: dynamic programming (DP) and belief propagation (BP) – meet with difficulties. Our recent concurrent propagation (CP), leaning upon the P systems paradigm, extends DP and BP to always detect whether the problem is ill posed or not and store in the ill-posed case an entire space of solutions that yield the same global optimum. This suggests a radically new path to proper regularisation: select the best-suited unique solution by exploring statistical and structural features of this space. We propose a P systems based implementation of CP and set out as a case study an application of CP to the image matching problem in stereo vision.

The paper presents SIGMA (Semantic Government Mash-up Application), a platform able to create mash-ups by providing access to open governmental data. The proposed solution is based on the existing semantic Web technologies (especially RDF and SPARQL) and uses public distributed endpoints conforming to the Linked Data initiative. Also, SIGMA allows creating and deployment of independent plugins, encouraging the developers to build innovative applications, visualization solutions and mash-ups that give an improved access to the governmental data.