Search

Tissue P systems with evolutional symport/antiport rules are a variant of tissue P systems, where objects are communicated through regions by symport/antiport rules, and objects may evolve during this process. It is known that such systems are able to solve NP problems in a polynomial time (and exponential space), when cell division is allowed. In this work, we continue to investigate the computational complexity aspects for tissue P systems with evolutional symport/antiport rules. We prove that problems beyond NP can also be solved. In particular, we show that deterministic systems of this type are able to solve all problems in the complexity class PP. Moreover, if non-deterministic systems are considered, then all problems in the class PSPACE can be solved.

Dynamic regulation of DNA origami nanostructures is important for the fabrication of intelligent DNA nanodevices. Toehold-mediated strand displacement is a common regulation strategy, which utilizes trigger strands to assemble and disassemble nanostructures. Such trigger strands are required to be completely complementary to the corresponding substrate strands, which strictly demands orthogonality and accuracy of the sequence design. Herein, we present a disassembly strategy of DNA origami dimers based on polymerase-triggered strand displacement, where the polymerase primers, as the trigger strands, were only partially complementary to the toehold region of the substrate strands. To demonstrate the programmability of trigger strands, we utilized primers with different sequence combination patterns to disassemble DNA origami dimers. The statistical summary of AFM images and fluorescence curves proved the feasibility of the new strategy. The utilization of polymerase-triggered strand displacement on the disassembly of DNA origami structures enriches the toolbox for the dynamic regulation of DNA nanostructures.

In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is an important task to tackle the P versus NP problem. Adding syntactic and/or semantic ingredients can mean passing from non-efficiency to presumed efficiency. Here, we try to get narrow frontiers, setting the stage to adapt efficient solutions from a family of P systems to another one. In order to do that, a solution to the problem is given by means of a family of tissue P systems with evolutional symport/antiport rules and cell separation with the restriction that both the left-hand side and the right-hand side of the rules have at most two objects; that is, with recognizer P systems from $${\mathcal {TSEC}}(2, 2)$$ TSEC ( 2 , 2 ) . This result improves a previous one, when 3 objects could be used in the left-hand side of the evolutional communication rules

Spiking neural P systems (abbreviated as SNP systems) are models of computation that mimic the behavior of biological neurons. The spiking neural P systems with communication on request (abbreviated as SNQP systems) are a recently developed class of SNP system, where a neuron actively requests spikes from the neighboring neurons instead of passively receiving spikes. It is already known that small SNQP systems, with four unbounded neurons, can achieve Turing universality. In this context, ‘unbounded’ means that the number of spikes in a neuron is not capped. This work investigates the dependency of the number of unbounded neurons on the computation capability of SNQP systems. Specifically, we prove that (1) SNQP systems composed entirely of bounded neurons can characterize the family of finite sets of numbers; (2) SNQP systems containing two unbounded neurons are capable of generating the family of semilinear sets of numbers; (3) SNQP systems containing three unbounded neurons are capable of generating nonsemilinear sets of numbers. Moreover, it is obtained in a constructive way that SNQP systems with two unbounded neurons compute the operations of Boolean logic gates, i.e., OR, AND, NOT, and XOR gates. These theoretical findings demonstrate that the number of unbounded neurons is a key parameter that influences the computation capability of SNQP systems.

The precursors of functional biomolecules in living cells are synthesized in a bottom-up manner and subsequently activated by modification into a delicate structure with near-atomic precision. DNA origami technology provides a promising way to mimic the synthesis of precursors, although mimicking the modification process is a challenge. Herein, a DNA paper-cutting (DNA kirigami) method to trim origami into designer nanostructures is proposed, where the modification is implemented by a polymerase-triggered DNA strand displacement reaction. Six geometric shapes are created by cutting rectangular DNA origami. Gel electrophoresis and atomic force microscopy results demonstrate the feasibility and capability of the DNA paper-cutting method. The proposed DNA paper-cutting strategy can enrich the toolbox for dynamically transforming DNA origami and has potential applications in biomimetics. .

Spiking neural P systems (SNP systems) are a class of distributed and parallel computation models, which are inspired by the way in which neurons process information by means of spikes, where a neuron fires and distributes the spikes to all the neurons linked by synapses with the firing neuron. In this work, a new spike distribution mechanism is introduced, where the produced spikes are distributed to a set of neurons indicated by the target indications. The computation power of SNP systems with this new spike distribution mechanism is investigated. It is demonstrated that SNP systems with such a distribution mechanism are Turing universal as both number generators and function computing devices. Moreover, it is shown that 6 neurons (respectively, 15 neurons) are sufficient for constructing a universal SNP system with the proposed spike distribution mechanism as a number generator (respectively, as a function computing device). By comparing with the classical one, it can be found that the proposed spike distribution mechanism is a powerful feature in terms of the number of neurons used to construct universal SNP systems.

Spiking neural P systems are a class of distributed parallel computing models, inspired by the way in which neurons process information and communicate with each other by means of spikes. In 2007, Freund and Verlan developed a formal framework for P systems to capture most of the essential features of P systems and to define their functioning in a formal way. In this work, we present an extension of the formal framework related to spiking neural P systems by considering the applicability of each rule to be controlled by specific conditions on the current contents of the cells. The main objective of this extension is to also capture spiking neural P systems in the formal framework. Another goal of our extension is to incorporate the notions of input and output. Finally, we also show that in the case of spiking neural P systems, the rules have a rather simple form and in that way spiking neural P systems correspond to vector addition systems where the application of rules is controlled by semi-linear sets.

With their complexity and vast search space, large-scale multiobjective optimization problems (LSMOPs) challenge existing multiobjective evolutionary algorithms (MOEAs). Recently, several large-scale multiobjective evolutionary algorithms have been developed to tackle LSMOPs. Unlike conventional MOEAs that concentrate on selection operations in the objective space, large-scale MOEAs emphasize operations in the decision space, such as offspring generation, to tackle the large number of decision variables. Nevertheless, most present large-scale MOEAs experience difficulty effectively and efficiently solving LSMOPs with tens of thousands or more decision variables or exhibit poor versatility in solving different LSMOPs. We propose a fast large-scale MOEA framework with reference-guided offspring generation, named FLEA, aiming at these issues. Generally, FLEA constructs several reference vectors in the decision space to steer the sampling of promising solutions during offspring generation. A parameter is used to allocate computation resources between the convergence and diversity of the offspring population adaptively. Without computationally expensive problem reformulation or decision variable analysis techniques, the proposed method can significantly accelerate the search speed of conventional MOEAs in solving LSMOPs. FLEA is examined on various LSMOPs with up to 1.6 million decision variables, demonstrating its superior effectiveness, efficiency, and versatility in large-scale multiobjective optimization.

Spiking neural P systems (SN P systems) refer to a type of distributed parallel neural computation model in the membrane computing framework. In this work, a new type of SN P system is examined, i.e., spiking neural P systems with polarizations (PSN P systems), by taking inspiration from the polarized cell membrane of a neuron. For the PSN P system, the firing condition of rules is the neuron-associated polarization. This work focuses on examining the computation power of the PSN P systems adopting the sequential mode induced by the minimum spike number, where at a computation step, one (resp., all) of neurons that hold the minimum spike number within the neurons which can fire will fire, i.e., the min-sequentiality strategy (resp., min-pseudo-sequentiality strategy). We prove that PSN P systems adopting the min-sequentiality strategy or min-pseudo-sequentiality strategy are Turing universal as the number generating devices. These results indicate the computation power of PSN P systems is robust regarding their strategies of sequentiality.

Toehold-mediated DNA strand displacement endows DNA nanostructures with dynamic response capability. However, the complexity of sequence design dramatically increases as the size of the DNA network increases. We attribute this problem to the mechanism of toehold-mediated strand displacement, termed exact strand displacement (ESD), in which one input strand corresponds to one specific substrate. In this work, we propose an alternative to toehold-mediated DNA strand displacement, termed fuzzy strand displacement (FSD), in which one-to-many and many-to-one relationships are established between the input strand and the substrate, to reduce the complexity. We have constructed four modules, termed converter, reporter, fuzzy detector, and fuzzy trigger, and demonstrated that a sequence pattern recognition network composed of these modules requires less complex sequence design than an equivalent network based on toehold-mediated DNA strand displacement.

Cell-like P systems where communication between the regions are carried out by rules of type symport/antiport are considered. These systems compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. The environment plays an active role in the sense that it not only can receive objects from the system, but also send objects into it. There is an alphabet associated with the environment whose elements appear in an arbitrary large number of copies at the initial configuration. This property seems too strong from a complexity view, but it has been widely exploited in the design of efficient solutions to computationally hard problems when some mechanisms (inspired by mitosis and membrane fission) allowing to construct an exponential workspace in linear time, are considered. In this paper, complexity aspects of P systems with symport/antiport rules and membrane division are considered when the set associated with the environment is the emptyset. It is shown that the role of the environment is irrelevant for such kind of P systems, in contrast with the well known results concerning to its relevance when membrane separation is used instead of membrane division.

Real-world systems interact with one another via dependency connectivities. Dependency connectivities make systems less robust because failures may spread iteratively among systems via dependency links. Most previous studies have assumed that two nodes connected by a dependency link are strongly dependent on each other; that is, if one node fails, its dependent partner would also immediately fail. However, in many real scenarios, nodes from different networks may be weakly dependent, and links may fail instead of nodes. How interdependent networks with weak dependency react to link failures remains unknown. In this paper, we build a model of fully interdependent networks with weak dependency and define a parameter α in order to describe the node-coupling strength. If a node fails, its dependent partner has a probability of failing of 1−α. Then, we develop an analytical tool for analyzing the robustness of interdependent networks with weak dependency under link failures, with which we can accurately predict the system robustness when 1−p fractions of links are randomly removed. We find that as the node coupling strength increases, interdependent networks show a discontinuous phase transition when ααc. Compared to site percolation with nodes being attacked, the crossover points αc are larger in the bond percolation with links being attacked. This finding can give us some suggestions for designing and protecting systems in which link failures can happen.

It is widely observed that life activities are regulated through conformational transitions of biological macromolecules, which inspires the construction of environmental responsive nanomachines in recent years. Here we present a thermal responsive DNA origami dimers system, whose conformations can be cyclically switched by thermal cycling. In our strategy, origami dimers are assembled at high temperatures and disassembled at low temperatures, which is different from the conventional strategy of breaking nanostructures using high temperatures. The advantage of this strategy is that the dimers system can be repeatedly operated without significant performance degradation, compared to traditional strategies such as conformational transitions via i-motif and G-quadruplexes, whose performance degrades with sample dilution due to repeated addition of trigger solutions. The cyclic conformational transitions of the dimers system are verified by fluorescence curves and AFM images. This research offered a new way to construct cyclic transformational nanodevices, such as reusable nanomedicine delivery systems or nanorobots with long service lifetimes.

Large-scale multiobjective optimization problems (LSMOPs) are challenging for existing approaches due to the complexity of objective functions and the massive volume of decision space. Some large-scale multiobjective evolutionary algorithms (LSMOEAs) have recently been proposed, which have shown their effectiveness in solving some benchmarks and real-world applications. They merely focus on handling the massive volume of decision space and ignore the complexity of LSMOPs in terms of objective functions. The complexity issue is also important since the complexity grows along with the increment in the number of decision variables. Our previous study proposed a framework to accelerate evolutionary large-scale multiobjective optimization via problem reformulation for handling large-scale decision variables. Here, we investigate the effectiveness of LSMOF combined with decomposition-based MOEA (MOEA/D), aiming to handle the complexity of LSMOPs in both the decision and objective spaces. Specifically, MOEA/D is embedded in LSMOF via two different strategies, and the proposed algorithm is tested on various benchmark LSMOPs. Experimental results indicate the encouraging performance improvement benefited from the solution of the complexity issue in large-scale multiobjective optimization.

This paper proposes a novel connected components labeling (CCL) approach that introduces a gamma signal to record certain mask pixels’ values to eliminate duplicated pixel checking and regulate the labeling process for higher efficiency. A new block-based two-scan CCL algorithm, Eight-Connected Gamma-Signal-regulated (ECGS) algorithm, is designed and developed by applying this approach to evaluate a block of 2 × 2 pixels (with just 6 mask pixels) in each iteration such that the total number of operations is considerably reduced and the labeling efficiency is significantly improved. The experiments conducted on a public benchmark, YACCLAB (Yet Another Connected Components Labeling Benchmark), have demonstrated that the proposed ECGS algorithm can outperform current state-of-the-art CCL algorithms for a number of digital images.

Spiking neural P systems (SN P systems) are a class of parallel computing models, inspired by the way in which neurons process information and communicate to each other by means of spikes. In this work, we consider a variant of SN P systems, SN P systems with polarizations (PSN P systems), where the integrate-and-fire conditions are associated with polarizations of neurons. The computation power of PSN P systems working in the asynchronous mode (at a computation step, a neuron with enabled rules does not obligatorily fire), instead of the synchronous mode (a neuron with enabled rules should fire), is investigated. We proved that asynchronous PSN P systems with extended rules (the application of a rule can produce more than one spikes) or standard rules (all rules can only produce a spike) can both characterize partially blind counter machines, hence, such systems are not Turing universal. The equivalence of the computation power of asynchronous PSN P systems in both cases of using extended rules or standard rules indicates that asynchronous PSN P systems are robust in terms of the amount of information exchanged among neurons. It is known that synchronous PSN P systems with standard rules are Turing universal, so these results also suggest that the working model, synchronization or asynchronization, is an essential ingredient for a PSN P system to achieve a powerful computation capability.

Spiking neural P systems (SN P systems) are a class of distributed and parallel neural-like computing models, inspired from the way neurons communicate by means of spikes. In this paper, a new variant of the systems, called SN P systems with learning functions, is introduced. Such systems can dynamically strengthen and weaken connections among neurons during the computation. A class of specific SN P systems with simple Hebbian learning function is constructed to recognize English letters. The experimental results show that the SN P systems achieve average accuracy rate 98.76% in the test case without noise. In the test cases with low, medium, and high noises, the SN P systems outperform back propagation neural networks and probabilistic neural networks. Moreover, comparing with spiking neural networks, SN P systems perform a little better in recognizing letters with noise. The result of this paper is promising in terms of the fact that it is the first attempt to use SN P systems in pattern recognition after many theoretical advancements of SN P systems, and SN P systems exhibit the feasibility for tackling pattern recognition problems.

Conventional switching ripple suppressor design methods require the domain expert to tune the design parameters, which is attributed to the multiple and complicated performance requirements and real-world restrictions in switching ripple suppressor design. However, the expert tuning method is time-consuming and inefficient, and the designed switching ripple suppressors under the given topology can only achieve a barely satisfactory performance which can be far from the optima. In this study, we propose a systematic design method from the perspective of many-objective optimization with constraints handling for high-performance switching ripple suppressor design. Meanwhile, an inductor-trap-inductor-capacitor-inductor (LTLCL) switching ripple suppressor is proposed for attenuating the harmonic currents around the multiple switching frequencies and guaranteeing − 60 dB/decades attenuation in the high-frequency bands. In the proposed design method, the LTLCL switching ripple suppressor design problem is treated as a many-objective optimization problem with constraints, and an evolutionary algorithm is designed to solve this problem, furthermore, a general decision making method is used to select the final design scheme. Experimental results have verified the admirable performance of the proposed switching ripple suppressor and the effectiveness of our design method.

Over the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). .ese borderlines can be seen as frontiers of efficiency, which are crucial in this methodology. “Translating,” in some sense, an efficient solution in a presumably efficient model to an efficient solution in a nonefficient model would give an affirmative answer to problem P versus NP. In the framework of Membrane Computing, the key of this approach is to detect the syntactic or semantic ingredients that are needed to pass from a nonefficient class of membrane systems to a presumably efficient one. .is paper deals with tissue P systems with communication rules of type symport/antiport allowing the evolution of the objects triggering the rules. In previous works, frontiers of efficiency were found in these kinds of membrane systems both with division rules and with separation rules. However, since they were not optimal, it is interesting to refine these frontiers. In this work, optimal frontiers of the efficiency are obtained in terms of the total number of objects involved in the communication rules used for that kind of membrane systems. .ese optimizations could be easier to translate, if possible, to efficient solutions in a nonefficient model. National Natural Science Foundation of China 61772214 National Natural Science Foundation of China 61602192 National Natural Science Foundation of China 61320106005 Hunan Provincial Natural Science Foundation of China 2020JJ4215 Agencia Estatal de Investigación TIN2017-89842-P

Mating restriction strategies are capable of restricting the distribution of parent solutions for effective offspring generation in evolutionary algorithms (EAs). Studies have shown the importance of these strategies in improving the performance of EAs for multiobjective optimization. Our previous study proposed a specific manifold learning inspired mating restriction (MLMR) strategy. It has shown promising capability of solving multiobjective optimization problems (MOPs) with complicated Pareto set shapes. However, the effect of mating restriction strategies in solving constrained MOPs is yet to be well studied. Here, we investigate the effectiveness of MLMR for solving constrained MOPs. The MLMR strategy is embedded into some representative multiobjective EAs and tested on various benchmark constrained MOPs. Experimental results indicate the encouraging performance of MLMR in constrained multiobjective optimization.

In nature, allostery is the principal approach for regulating cellular processes and pathways. Inspired by nature, structure-switching aptamer-based nanodevices are widely used in artificial biotechnologies. However, the canonical aptamer structures in the nanodevices usually adopt a duplex form, which limits the flexibility and controllability. Here, a new regulating strategy based on a clamp-like triplex aptamer structure (CLTAS) was proposed for switching DNA polymerase activity via conformational changes. It was demonstrated that the polymerase activity could be regulated by either adjusting structure parameters or dynamic reactions including strand displacement or enzymatic digestion. Compared with the duplex aptamer structure, the CLTAS possesses programmability, excellent affinity and high discrimination efficiency. The CLTAS was successfully applied to distinguish single-base mismatches. The strategy expands the application scope of triplex structures and shows potential in biosensing and programmable nanomachines.

Asynchronous tissue P systems with symport/antiport rules are a class of parallel computing models inspired by cell tissue working in a non-synchronized way, where the use of rules is not obligatory, that is, at a computation step, an enabled rule may or may not be applied. In this work, the notion of local synchronization is introduced at three levels: rules, channels, and cells. If a rule in a locally synchronous set of rules (resp., cells or channels) is used, then all enabled rules in the same locally synchronous set of rules (resp., whose involved channels or cells) should be applied in a maximally parallel manner and the implementation of these rules is finished in one computation step. The computational power of local synchronization on asynchronous tissue P systems with symport/antiport rules at the three levels is investigated. It is shown that asynchronous tissue P systems with symport/antiport rules and with locally synchronous sets of rules, channels, or cells are all Turing universal. By comparing the computational power of asynchronous tissue P systems with or without local synchronization, it can be found that the local synchronization is a useful tool to achieve a desired computational power.

In the majority of models of P systems, rules are applied at the ticks of a global clock and their products are introduced into the system for the following step. In timed P systems, di erent integer durations are statically assigned to rules; time-free P systems are P systems yielding the same languages independently of these durations. In clock-free P systems, durations are real and are assigned to individual rule applications; thus, different applications of the same rule may last for a different amount of time. In this paper, we formalise timed, time-free, and clock-free P system within a framework for generalised parallel rewriting. We then explore the relationship between these variants of semantics. We show that clock-free P systems cannot effi ciently solve intractable problems. Moreover, we consider un-timed systems where we collect the results using arbitrary timing functions as well as un-clocked P systems where we take the union over all possible per-instance rule durations. Finally, we also introduce and study mode-free P systems, whose results do not depend on the choice of a mode within a fixed family of modes, and compare mode-freeness with clock-freeness.

Traditional neuron models use analog values for information representation and computation, while all-or-nothing spikes are employed in the spiking ones. With a more brain-like processing paradigm, spiking neurons are more promising for improvements on efficiency and computational capability. They extend the computation of traditional neurons with an additional dimension of time carried by all-or-nothing spikes. Could one benefit from both the accuracy of analog values and the time-processing capability of spikes? In this paper, we introduce a concept of augmented spikes to carry complementary information with spike coefficients in addition to spike latencies. New augmented spiking neuron model and synaptic learning rules are proposed to process and learn patterns of augmented spikes. We provide systematic insight into the properties and characteristics of our methods, including classification of augmented spike patterns, learning capacity, construction of causality, feature detection, robustness and applicability to practical tasks such as acoustic and visual pattern recognition. The remarkable results highlight the effectiveness and potential merits of our methods. Importantly, our augmented approaches are versatile and can be easily generalized to other spike-based systems, contributing to a potential development for them including neuromorphic computing., Comment: 13 pages

P systems with active membranes are a class of computation models in the area ofmembrane computing, which are inspired from the mechanism by which chemicalsinteract and cross cell membranes. In this work, we consider a normal form of P systemswith active membranes, called cell-like P systems with polarizations and minimal rules,where rules are minimal in the sense that an object evolves to exactly one object withthe application of an evolution rule or a communication rule, or an object evolves to twoobjects that are assigned to the two new generated membranes by applying a division rule.The present work investigates the computational power of P systems with polarizationsand minimal rules. Specifically, results about Turing universality and non-universality areobtained with the combination of the number of membranes, the number of polarizations,and the types of rules. We also show that polarizationless P systems with minimal rules areequivalent to Turing machines working in a polynomial space, that is, the class of problemsthat can be solved in polynomial time by polarizationless P systems with minimal rules isequal to the classPSPACE. Ministerio de Economía, Industria y Competitividad TIN2017-89842-P (MABICAP)

Under certain smoothness assumptions, the Pareto set of a continuous multiobjective optimization problem is a piecewise continuous manifold in the decision space, which can be derived from the Karush–Kuhn–Tucker condition. Despite that a number of multiobjective evolutionary algorithms (MOEAs) have been proposed, their performance on multiobjective optimization problems with complicated Pareto sets (MOP-cPS) is still unsatisfying. In this article, we adopt the concept of manifold and propose a manifold learning-inspired mating strategy to enhance the diversity maintenance in MOEAs for solving MOP-cPS efficiently. In the proposed strategy, all of the individuals are first clustered into different manifolds according to their distribution in the objective space, and then the mating reproduction is restricted among individuals in the same manifold. Moreover, we embed the proposed mating strategy in three representative MOEAs and compare the embedded MOEAs with their original versions using the assortative genetic operators on a variety of MOP-cPS. The experimental results demonstrate the significant performance improvements benefitting from the proposed mating restriction strategy.

Tissue P systems with channel states are a class of parallel computing models, where the communication between two regions is regulated by a channel state, and at a computation step the state of a channel can evolve to one of the arbitrarily many states. In this work, we limit the “arbitrarily many states of a channel” to “two states of a channel”. Such a variant of P systems is called tissue P systems with flip-flop channel states (TPFFCSs). The computation power of TPFFCSs is studied. We show that TPFFCSs with arbitrarily many cells and antiport rules of length 2 are able to compute only finite sets of non-negative integers. However, TPFFCSs with two cells, antiport rules of length 3, or symport rules of length 2, or symport rules of length 1 and antiport rules of length 2 are proved to be Turing universal.

Contextual array P systems generate two-dimensional picture arrays by sequential application of contextual array rules on picture arrays. Here we consider a parallel mode of application of the contextual array rules in the regions of such an array P system. We call the resulting array P system as parallel contextual array P system (PCAP) and we study the generative power of these systems. A main advantage is that the number of membranes needed in the constructions of the PCAP for picture array generation is reduced in comparison with the sequential counterpart.

Identification of essential proteins plays an important role for understanding the cellular life activity and development in postgenomic era. Identification of essential proteins from the protein-protein interaction (PPI) networks has become a hot topic in recent years. In this work, fruit fly optimization algorithm (FOA) is extended for identifying essential proteins, the extended algorithm is called EPFOA, which merges FOA with topological properties and biological information for essential proteins identification. The algorithm EPFOA has the advantage of identifying multiple essential proteins simultaneously rather than completely relying on ranking score identification individually. The performance of EPFOA is analyzed on dynamic PPI networks, which are constructed by combining the gene expression data. The experimental results demonstrate that EPFOA is more efficient in detecting essential proteins than the state-of-the-art essential proteins detection methods.

Tissue P systems with evolutional communication rules and cell division (TPec, for short) are a class of bio-inspired parallel computational models, which can solve NP-complete problems in a feasible time. In this work, a variant of TPec, called $k$-distributed tissue P systems with evolutional communication and cell division ($k\text{-}\Delta_{TP_{ec}}$, for short) is proposed. A uniform solution to the SAT problem by $k\text{-}\Delta_{TP_{ec}}$ under balanced fixed-partition is presented. The solution provides not only the precise satisfying truth assignments for all Boolean formulas, but also a precise amount of possible such satisfying truth assignments. It is shown that the communication resource for one-way and two-way uniform $k$-P protocols are increased with respect to $k$; while a single communication is shown to be possible for bi-directional uniform $k$-P protocols for any $k$. We further show that if the number of clauses is at least equal to the square of the number of variables of the given boolean formula, then $k\text{-}\Delta_{TP_{ec}}$ for solving the SAT problem are more efficient than TPec as show in \cite{bosheng2017}; if the number of clauses is equal to the number of variables, then $k\text{-}\Delta_{TP_{ec}}$ for solving the SAT problem work no much faster than TPec.

Numerical P systems (NP systems) are a class of computing models inspired both from the structure of living cells and the economic reality. Enzymatic numerical P systems (ENP systems) are a variant of NP systems, which were successfully applied in autonomous robot control. In this work, we investigate the computational power of ENP systems working in the sequential mode: both non-deterministically sequential and deterministically sequential systems are considered. For non-deterministically sequential ENP systems, we improve a known universality result by reducing the number of membranes and programs used in the universal system from 7 to 2 and 19 to 8, respectively. For deterministically sequential ENP systems, we prove that they are Turing universal even when linear production functions are used and each function has at most two variables. As a byproduct, we obtain a small deterministic universal enzymatic numerical P system with 23 membranes and 118 programs by simulating a specific universal register machine. These results give a positive answer to an open problem formulated in Gh. Paun (2014) [37] .

An operation on strings, called flat splicing was introduced, inspired by a splicing operation on circular strings considered in the study of modelling of the recombinant behaviour of DNA molecules. A simple kind of flat splicing, called alphabetic flat splicing, allows insertion of a word with a specified start symbol and/or a specified end symbol, between two pre-determined symbols in a given word. In this work, we consider a P system with only alphabetic flat splicing rules as the evolution rules and strings of symbols as objects in its regions. We examine the language generative power of the resulting alphabetic flat splicing P systems (AFS P systems, for short). In particular, we show that AFS P systems with two membranes are more powerful in generative power than AFS P systems with a single membrane. We also construct AFS P systems with at most three membranes to generate languages that do not belong to certain other language classes and show an application to generation of chain code pictures.

Maximally parallel manner is a usual rule application strategy for P systems, where rules should be used in parallel to the maximum degree possible. In this work, we consider a rule application strategy, rule synchronization, where some synchronization sets of rules are given, a rule in a synchronization set of rules can be applied only if all rules in the set are enabled. Tissue P systems with synchronized symport/antiport rules and synchronization sets of rules are called tissue P systems with synchronized symport/antiport rules. We prove that tissue P systems with synchronized symport/antiport rules consisting of only one cell are universal. Besides, we prove that the SAT problem can be solved by the proposed tissue P systems when cell division rules are introduced. The results show that synchronization over rules is a rule application strategy that can increase the computational power of tissue P systems with symport/antiport rules.

Community detection is an important tool to analyze hidden information such as functional module and topology structure in complex networks. Compared with traditional community detection, it is more challenging to find overlapping communities in complex networks, especially when the networks are of large scales. Among various overlapping community detection techniques, the well-known clique percolation method (CPM) has shown promising performance in terms of quality of found communities, but suffers from serious curse of dimensionality due to its high computational complexity, which makes it very unlikely to be applied to large-scale networks. To address this issue, in this paper, we propose a weak-CPM for overlapping community detection in large-scale networks. A new measure for characterizing the similarity between weak cliques is also suggested to check whether the weak cliques can be merged into a community. Experimental results on synthetic and real-world networks demonstrate the competitive performance of the proposed method over six popular overlapping community detection algorithms in terms of both computational efficiency and quality of found communities. In addition, the proposed method is also suitable for detecting large-scale networks with an unclear community structure under different levels of overlapping density and overlapping diversity, which is an important property of many real-world complex networks.

This paper investigates the cluster synchronization problem of coupled delayed competitive neural networks (CNNs) with two time scales. Each CNN contains short- and long-term memories, which can be regarded as the fast and slow dynamics, respectively. Besides, a general communication topology that describes both cooperation and competition in CNN-to-CNN relations is considered along with fixed and adaptive coupling schemes. The interactive relationship between the fast and slow dynamics as well as the effects of the fast time scale on synchronization behavior has not been fully exploited in existing Lyapunov functionals. Moreover, the results from pervious works are limited to the master–slave synchronization of two CNNs. In this paper, a novel Lyapunov–Krasovskii functional is proposed to solve the cluster synchronization problem under the fixed coupling scheme. The coupled delayed CNNs within a specific range of the fast time scale achieve a desirable behavior when the coupling and pinning strengths are chosen properly. Furthermore, to facilitate the selection of these strengths, an adaptive pinning controller is designed and a modified Lyapunov–Krasovskii functional is also constructed for coupled delayed CNNs with two time scales. Finally, several numerical examples are provided to demonstrate the effectiveness of the theoretical results.

Calibration devices in an automatic verification system are used to verify the accuracy of electricity smart meters. As time goes by, calibration devices may experience the metering performance degradation, making results of error tests biased. Therefore, it is of great significance to ensure calibration devices have qualified metering performance. Conventionally, their performance could only be manually inspected at regular intervals, while keep unknown during the operation. To address this issue, an on-line anomaly identifying method based on calibration devices’ parallel working mode is proposed to check their metering performance in real time. Instead of off-line inspections, a device’s metering performance is associated with the corresponding results of error tests, and comparisons among distributions based on results corresponding to different calibration devices would provide evidences to identify the ones having metering performance unqualified without interrupting the verification tasks. In addition, a case study is conducted to prove the validity.

Constrained multiobjective optimization problems (CMOPs) are widespread in real-world applications. Nevertheless, CMOPs with discontinuous feasible regions are challenging for existing evolutionary algorithms due to the difficulty of passing through the infeasible regions. Moreover, there are only several benchmark test problems specified for promoting the research in complex constrained multiobjective optimization. To address these two issues, we first propose a set of CMOPs with discontinuous feasible regions by introducing constraints into the widely used DTLZ test problems, and then a pioneer selection strategy is designed to handle these complex constrained optimization problems. The general idea of the proposed constraint handling strategy is simple, which selects some individuals in the population as the pioneer population, aiming to obtain some well-converged solutions without considering the constraints. By adjusting the ratio of the pioneer solutions during the evaluation, the quasi-optimal solutions are expected to approximate the Pareto optimal front. To investigate the performance of the proposed strategy, it is embedded in a classic evolutionary algorithm and compared with three state-of-the-art constrained multiobjective evolutionary algorithms. Experimental results demonstrate the effectiveness of the proposed strategy and also show that the proposed benchmark problems are challenging for existing approaches.

Community detection problem in networks has received a great deal of attention during the past decade. Most of community detection algorithms took into account only positive links, but they are not suitable for signed networks. In our work, we propose an algorithm based on random walks for community detection in signed networks. Firstly, the local maximum degree node which has a larger degree compared with its neighbors is identified, and the initial communities are detected based on local maximum degree nodes. Then, we calculate a probability for the node to be attracted into a community by positive links based on random walks, as well as a probability for the node to be away from the community on the basis of negative links. If the former probability is larger than the latter, then it is added into a community; otherwise, the node could not be added into any current communities, and a new initial community may be identified. Finally, we use the community optimization method to merge similar communities. The proposed algorithm makes full use of both positive and negative links to enhance its performance. Experimental results on both synthetic and real-world signed networks demonstrate the effectiveness of the proposed algorithm.