50 results on '"Linqiang Pan"'
Search Results
2. Spiking neural P systems with target indications
- Author
-
Linqiang Pan, Tingfang Wu, and Luping Zhang
- Subjects
Quantitative Biology::Neurons and Cognition ,General Computer Science ,Distribution (number theory) ,Computer science ,Computation ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,01 natural sciences ,Theoretical Computer Science ,Power (physics) ,Set (abstract data type) ,Synapse ,Computer Science::Emerging Technologies ,medicine.anatomical_structure ,nervous system ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Feature (machine learning) ,medicine ,020201 artificial intelligence & image processing ,Spike (software development) ,Neuron ,Biological system - Abstract
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.
- Published
- 2021
3. The computation power of spiking neural P systems with polarizations adopting sequential mode induced by minimum spike number
- Author
-
Linqiang Pan and Tingfang Wu
- Subjects
0209 industrial biotechnology ,Quantitative Biology::Neurons and Cognition ,Computer science ,Cognitive Neuroscience ,Computation ,02 engineering and technology ,Topology ,Computer Science Applications ,020901 industrial engineering & automation ,Models of neural computation ,Membrane ,medicine.anatomical_structure ,Polarized cell ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,medicine ,020201 artificial intelligence & image processing ,Neuron ,Membrane computing ,P system - Abstract
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.
- Published
- 2020
4. P systems with symport/antiport rules: When do the surroundings matter?
- Author
-
Bosheng Song, Linqiang Pan, Miguel A. Martínez-del-Amor, Luis Valencia-Cabrera, David Orellana-Martín, and Mario J. Pérez-Jiménez
- Subjects
Property (philosophy) ,Membrane ,General Computer Science ,Membrane fission ,Computational complexity theory ,Computer science ,Division (mathematics) ,Type (model theory) ,Topology ,Membrane computing ,Time complexity ,Theoretical Computer Science - Abstract
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.
- Published
- 2020
5. Multiobjective trajectory optimization with a cutting and padding encoding strategy for single-UAV-assisted mobile edge computing system
- Author
-
Jianqing Lin and Linqiang Pan
- Subjects
General Computer Science ,General Mathematics - Published
- 2022
6. A gamma-signal-regulated connected components labeling algorithm
- Author
-
Linqiang Pan, Danyang Zhang, and Huadong Ma
- Subjects
Connected component ,Pixel ,Computer science ,Process (computing) ,02 engineering and technology ,01 natural sciences ,Signal ,Digital image ,Artificial Intelligence ,0103 physical sciences ,Signal Processing ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,020201 artificial intelligence & image processing ,Computer Vision and Pattern Recognition ,010306 general physics ,Algorithm ,Software ,Block (data storage) - Abstract
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.
- Published
- 2019
7. Computation power of asynchronous spiking neural P systems with polarizations
- Author
-
Tingfang Wu, Artiom Alhazov, and Linqiang Pan
- Subjects
General Computer Science ,Computer science ,Computation ,0102 computer and information sciences ,02 engineering and technology ,Topology ,01 natural sciences ,Synchronization ,Theoretical Computer Science ,Power (physics) ,medicine.anatomical_structure ,010201 computation theory & mathematics ,Asynchronous communication ,0202 electrical engineering, electronic engineering, information engineering ,medicine ,020201 artificial intelligence & image processing ,Spike (software development) ,Neuron ,Turing ,computer ,Equivalence (measure theory) ,P system ,computer.programming_language - Abstract
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.
- Published
- 2019
8. Switching ripple suppressor design of the grid-connected inverters: A perspective of many-objective optimization with constraints handling
- Author
-
Jinbang Xu, Jie Ye, Linqiang Pan, Zhixiong Zhang, and Cheng He
- Subjects
Optimization problem ,General Computer Science ,Computer science ,General Mathematics ,05 social sciences ,Ripple ,Evolutionary algorithm ,050301 education ,Topology (electrical circuits) ,02 engineering and technology ,Grid ,Subject-matter expert ,Control theory ,0202 electrical engineering, electronic engineering, information engineering ,Harmonic ,020201 artificial intelligence & image processing ,Design methods ,0503 education - Abstract
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.
- Published
- 2019
9. Guest editorial introduction to the special section on bio-inspired computing – emerging theories and industry applications
- Author
-
Xiaochun Cheng, Mario J Pérez Jiménez, Linqiang Pan, and Shudong Wang
- Subjects
General Computer Science ,Control and Systems Engineering ,Electrical and Electronic Engineering - Published
- 2022
10. Neighborhood-based particle swarm optimization with discrete crossover for nonlinear equation systems
- Author
-
Linqiang Pan, Yi Zhao, and Lianghao Li
- Subjects
General Computer Science ,General Mathematics - Published
- 2022
11. The computational power of enzymatic numerical P systems working in the sequential mode
- Author
-
Yansen Su, Zhiqiang Zhang, and Linqiang Pan
- Subjects
Theoretical computer science ,General Computer Science ,Computer science ,Open problem ,0102 computer and information sciences ,02 engineering and technology ,Autonomous robot ,01 natural sciences ,Theoretical Computer Science ,Universality (dynamical systems) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Turing ,computer ,P system ,Register machine ,computer.programming_language - Abstract
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] .
- Published
- 2018
12. Language generating alphabetic flat splicing P systems
- Author
-
Linqiang Pan, Bosheng Song, K. G. Subramanian, and Atulya K. Nagar
- Subjects
Chain code ,General Computer Science ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,Construct (python library) ,01 natural sciences ,Theoretical Computer Science ,010201 computation theory & mathematics ,Symbol (programming) ,Simple (abstract algebra) ,RNA splicing ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Arithmetic ,Word (computer architecture) - Abstract
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.
- Published
- 2018
13. Rule synchronization for tissue P systems
- Author
-
Linqiang Pan and Bosheng Song
- Subjects
Set (abstract data type) ,Computational Theory and Mathematics ,If and only if ,Computer science ,Synchronization (computer science) ,Topology ,Computer Science Applications ,Information Systems ,Theoretical Computer Science ,Power (physics) - Abstract
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.
- Published
- 2021
14. An on-line anomaly identifying method for calibration devices in an automatic verification system for electricity smart meters
- Author
-
Linqiang Pan, Zhiwei Bao, Qing Chen, Hongbin Li, and Yang Jiao
- Subjects
Calibration (statistics) ,business.industry ,Computer science ,Applied Mathematics ,Anomaly (natural sciences) ,020208 electrical & electronic engineering ,010401 analytical chemistry ,Real-time computing ,Mode (statistics) ,Verification system ,02 engineering and technology ,Condensed Matter Physics ,01 natural sciences ,Line (electrical engineering) ,0104 chemical sciences ,0202 electrical engineering, electronic engineering, information engineering ,Metering mode ,Electricity ,Electrical and Electronic Engineering ,business ,Instrumentation - Abstract
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.
- Published
- 2021
15. Pioneer selection for evolutionary multiobjective optimization with discontinuous feasible region
- Author
-
Cheng He, Wenting Xu, Lianghao Li, and Linqiang Pan
- Subjects
Mathematical optimization ,education.field_of_study ,General Computer Science ,Computer science ,General Mathematics ,05 social sciences ,Feasible region ,Population ,Evolutionary algorithm ,050301 education ,02 engineering and technology ,Multi-objective optimization ,Set (abstract data type) ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,020201 artificial intelligence & image processing ,education ,0503 education ,Constraint (mathematics) ,Selection (genetic algorithm) - Abstract
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.
- Published
- 2021
16. Numerical P systems with production thresholds
- Author
-
Zhiqiang Zhang, Jinbang Xu, Linqiang Pan, and Tingfang Wu
- Subjects
Mathematical optimization ,General Computer Science ,Computer program ,Computation ,0102 computer and information sciences ,02 engineering and technology ,Production function ,021001 nanoscience & nanotechnology ,Economic reality ,01 natural sciences ,Theoretical Computer Science ,Universality (dynamical systems) ,Robot control ,010201 computation theory & mathematics ,0210 nano-technology ,Behavior-based robotics ,Algorithm ,Membrane computing ,Mathematics - Abstract
Numerical P systems (for short, NP systems) are distributed and parallel computing models inspired both from the structure of living cells and from the economic reality, where the values of variables evolve by programs that are composed by production functions and repartition protocols: the value of a production function is distributed to variables according to the corresponding repartition protocol. In this work, we introduce a new method of using evolution programs into NP systems, where thresholds are associated with production functions. The computation power of NP systems with production thresholds is investigated. Specifically, we prove that NP systems with lower-thresholds (the production function value can be distributed only when it is not smaller than a given constant), with one membrane working both in the all-parallel mode and in the sequential mode, are universal. The universal results of NP systems with lower-thresholds are extended to NP systems with upper-thresholds (the production function value can be distributed only when it is not greater than a given constant) by simulating the former with the latter. These universality results show that NP systems with production thresholds have the potential to implement any computer program or robot behavior.
- Published
- 2017
17. Tissue-like P systems with evolutional symport/antiport rules
- Author
-
Linqiang Pan, Bosheng Song, and Cheng Zhang
- Subjects
Information Systems and Management ,0102 computer and information sciences ,02 engineering and technology ,Topology ,01 natural sciences ,Computer Science Applications ,Theoretical Computer Science ,010201 computation theory & mathematics ,Artificial Intelligence ,Control and Systems Engineering ,Symporter ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Bio-inspired computing ,Algorithm ,Membrane computing ,Software ,Mathematics - Abstract
Tissue P systems with symport/antiport rules are a class of distributed parallel computing models inspired by the cell intercommunication in tissues, where objects are never modified in the process of communication, just changing their place within the system. In this work, a variant of tissue P systems, called tissue P systems with evolutional symport/antiport rules is introduced, where objects are moved from one region to another region and may be evolved during this process. The computational power of such P systems is studied. Specifically, it is proved that such P systems with one cell and using evolutional symport rules of length at most 3 or using evolutional antiport rules of length at most 4 are Turing universal (only the family of all finite sets of positive integers can be generated by such P systems if standard symport/antiport rules are used). Moreover, cell division rules are considered in tissue P systems with evolutional symport/antiport rules, and a limit on the efficiency of such P systems is provided with evolutional communication rules of length at most 2. The computational efficiency of this kind of models is shown when using evolutional communication rules of length at most 4.
- Published
- 2017
18. Adaptive simulated binary crossover for rotated multi-objective optimization
- Author
-
Wenting Xu, Ran Cheng, Cheng He, Lianghao Li, and Linqiang Pan
- Subjects
Mathematical optimization ,Optimization problem ,General Computer Science ,Property (programming) ,Computer science ,General Mathematics ,05 social sciences ,Crossover ,Evolutionary algorithm ,Pareto principle ,050301 education ,Binary number ,02 engineering and technology ,Multi-objective optimization ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,0503 education ,Rotation (mathematics) - Abstract
Crossover is a crucial operation for generating promising offspring solutions in evolutionary multi-objective optimization. Among various crossover operators, the simulated binary crossover (SBX) is the most widely used in evolutionary multi-objective optimization. Despite that SBX is effective in solving problems with regular Pareto sets, its performance degenerates dramatically on problems with rotated Pareto sets.To address this issue, we propose a modified SBX, named the rotation-based simulated binary crossover (RSBX), to improve the performance of multi-objective evolutionary algorithms (MOEAs) on rotated problems whose Pareto sets are not parallel with the decision variables. The main idea is to introduce the rotation property into the SBX, and then an adaptive selection strategy is proposed to make use of both SBX and RSBX. The proposed method is embedded in three representative MOEAs, and they are compared with their original versions on some problems with rotated Pareto sets, respectively. Experimental results demonstrate that the proposed method is efficient in promoting the performance of conventional MOEAs for handling rotated multi-objective optimization problems.
- Published
- 2021
19. Numerical P systems with migrating variables
- Author
-
Andrei Păun, Zhiqiang Zhang, Tingfang Wu, and Linqiang Pan
- Subjects
Discrete mathematics ,General Computer Science ,Computer science ,Chomsky hierarchy ,Computation ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Universality (dynamical systems) ,Recursively enumerable language ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Bio-inspired computing ,Membrane computing ,Generative grammar - Abstract
Numerical P systems are a class of P systems inspired both from the structure of living cells and from economics, where variables are associated with the membranes, and these associations are not changed during the computation. However, in the standard P systems, a crucial character for objects is that they can pass through membranes, between regions of the same cell, between cells, or between cells and their environment. We introduce this character also to numerical P systems, and call the new variant numerical P systems with migrating variables (MNP systems). The computational power of MNP systems is investigated both as number generators and as string generators, working in the one-parallel or the sequential modes. Specially, as number generators, MNP systems are proved to be universal working in the above two modes. As string generators, the generative capacity of such systems is investigated having as a reference the families of languages in the Chomsky hierarchy, and a characterization of recursively enumerable languages is obtained.
- Published
- 2016
20. Controllability of the better chosen partial networks
- Author
-
Linqiang Pan and Xueming Liu
- Subjects
0301 basic medicine ,Statistics and Probability ,Dynamic network analysis ,Computer science ,Interdependent networks ,Distributed computing ,0206 medical engineering ,Gene regulatory network ,02 engineering and technology ,Complex network ,Condensed Matter Physics ,Controllability ,03 medical and health sciences ,030104 developmental biology ,Evolving networks ,Interaction network ,Hierarchical network model ,020602 bioinformatics ,Biological network - Abstract
How to control large complex networks is a great challenge. Recent studies have proved that the whole network can be sufficiently steered by injecting control signals into a minimum set of driver nodes, and the minimum numbers of driver nodes for many real networks are high, indicating that it is difficult to control them. For some large natural and technological networks, it is impossible and not feasible to control the full network. For example, in biological networks like large-scale gene regulatory networks it is impossible to control all the genes. This prompts us to explore the question how to choose partial networks that are easy for controlling and important in networked systems. In this work, we propose a method to achieve this goal. By computing the minimum driver nodes densities of the partial networks of Erdos–Renyi (ER) networks, scale-free (SF) networks and 23 real networks, we find that our method performs better than random method that chooses nodes randomly. Moreover, we find that the nodes chosen by our method tend to be the essential elements of the whole systems, via studying the nodes chosen by our method of a real human signaling network and a human protein interaction network and discovering that the chosen nodes from these networks tend to be cancer-associated genes. The implementation of our method shows some interesting connections between the structure and the controllability of networks, improving our understanding of the control principles of complex systems.
- Published
- 2016
21. Spiking neural P systems with request rules
- Author
-
Linqiang Pan and Tao Song
- Subjects
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES ,Forgetting ,Theoretical computer science ,Computer science ,Cognitive Neuroscience ,Computation ,Small number ,Natural number ,0102 computer and information sciences ,02 engineering and technology ,ComputerSystemsOrganization_PROCESSORARCHITECTURES ,01 natural sciences ,Computer Science Applications ,medicine.anatomical_structure ,Computable function ,010201 computation theory & mathematics ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,medicine ,020201 artificial intelligence & image processing ,Neuron ,Membrane computing ,Turing ,computer ,computer.programming_language - Abstract
Spiking neural P systems, shortly called SN P systems, are a class of distributed and parallel neural-like computing models, inspired from the way of neurons spiking and communicating with each other by means of spikes. In this work, we propose a new variant of SN P systems, called SN P systems with request rules. In such a system, besides spiking and forgetting rules, a neuron can have request rules, with which the neuron can sense "stimulus" from the environment by receiving a certain number of spikes. We investigate the computation power of SN P systems with request rules. It is obtained that such systems are Turing universal, even with a small number of neurons. Specifically, (i) SN P systems with request rules having 4 neurons can compute any set of Turing computable natural numbers and (ii) with 47 neurons such systems can compute any Turing computable function.
- Published
- 2016
22. Cell-like spiking neural P systems
- Author
-
Linqiang Pan, Zhiqiang Zhang, Gheorghe Pun, and Tingfang Wu
- Subjects
Spiking neural network ,Theoretical computer science ,General Computer Science ,business.industry ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Random neural network ,Theoretical Computer Science ,Universality (dynamical systems) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,Bio-inspired computing ,business ,Membrane computing - Abstract
With mathematical motivation, we consider a combination of basic features of multiset-rewriting P systems and of spiking neural P systems, that is, we consider cell-like P systems with spiking rules in their membranes (hence dealing with only one kind of objects, the spikes). The universality of these systems as number generating devices is proved for the two usual ways to define the output (internally or externally) and for various restrictions on the spiking rules. Several research topics are also pointed out.
- Published
- 2016
23. Flat maximal parallelism in P systems with promoters
- Author
-
Linqiang Pan, Bosheng Song, and Gheorghe Paun
- Subjects
Discrete mathematics ,General Computer Science ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Universality (dynamical systems) ,Combinatorics ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Turing universality ,020201 artificial intelligence & image processing ,Maximal set ,Membrane computing ,Turing ,computer ,P system ,Mathematics ,Sat problem ,computer.programming_language - Abstract
In spite of the fact that many ways of using the evolution rules in a P system were already investigated, there is still a case, which we call the flat maximal parallelism, which appeared in several papers, but which deserves a more careful attention: in each step, in each membrane, a maximal set of applicable rules is chosen and each rule in the set is applied exactly once. In this work, flat maximal parallelism is studied for non-cooperating P systems with promoters. Specifically, we prove that non-cooperating P systems with at most one promoter associated with any rule, working in the flat maximally parallel way, are Turing universal (the Turing universality of such P systems is open if they work in the maximally parallel way). Moreover, a uniform solution to the SAT problem is provided by using non-cooperating P systems with promoters and membrane division, working in the flat maximal parallel way.
- Published
- 2016
24. Spiking neural P systems with anti-spikes working in sequential mode induced by maximum spike number
- Author
-
Keqin Jiang and Linqiang Pan
- Subjects
Cognitive Neuroscience ,0102 computer and information sciences ,02 engineering and technology ,Inhibitory postsynaptic potential ,01 natural sciences ,Computer Science Applications ,medicine.anatomical_structure ,010201 computation theory & mathematics ,Artificial Intelligence ,Inhibitory synapses ,0202 electrical engineering, electronic engineering, information engineering ,medicine ,020201 artificial intelligence & image processing ,Neuron ,Membrane computing ,Algorithm ,Mathematics - Abstract
Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired by spiking neurons. SN P systems with anti-spikes (ASN P systems) are a variant of SN P systems, which were inspired by inhibitory impulses/spikes or inhibitory synapses. In this work, we consider ASN P systems with the restrictions: (1) systems are simple in the sense that each neuron has only one rule; (2) at each step the neuron(s) with the maximum number of spikes among the neurons that are active (can spike) will fire; (3) the feature of delays and forgetting rules are not used. These restrictions make the systems working in a sequential way. We investigate the computational power of ASN P systems under these restrictions. Specifically, we prove that such systems with spiking rules of categories ( a , a ) and ( a , a ? ) are universal as both number generating and accepting devices. We also prove that ASN P systems with inhibitory synapses using spiking rules of category ( a , a ) are universal as both generating and accepting devices. These results show that ASN P systems are still powerful working with these restrictions.
- Published
- 2016
25. Spiking neural P systems with homogeneous neurons and synapses
- Author
-
Yuzhou Zhang, Keqin Jiang, Wenli Chen, and Linqiang Pan
- Subjects
Spiking neural network ,Theoretical computer science ,Quantitative Biology::Neurons and Cognition ,Cognitive Neuroscience ,0102 computer and information sciences ,02 engineering and technology ,Topology ,01 natural sciences ,Random neural network ,Computer Science Applications ,Synapse ,Computer Science::Emerging Technologies ,010201 computation theory & mathematics ,Artificial Intelligence ,Homogeneous ,0202 electrical engineering, electronic engineering, information engineering ,Process information ,020201 artificial intelligence & image processing ,Bio-inspired computing ,Membrane computing ,P system ,Mathematics - Abstract
Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons process information and communicate by means of spikes, where neurons are different in the sense that they can have different sets of spiking rules. In this work, we consider a variant of SN P systems with two restrictions: (1) all neurons contain only spikes (neurons are homogeneous in this case, since they can be considered as containers of spikes), while the spiking rules are moved on the synapses; (2) all synapses are homogeneous in the sense that each synapse has the same set of rules. These restrictions correspond to the fact that the SN P system consists of only one kind of neurons and one kind of synapses. The computational power of SN P systems with homogeneous neurons and synapses is investigated. Specifically, it is proved that such systems are Turing universal as both number generating and number accepting devices.
- Published
- 2016
26. Guest editorial special issue on collaborative learning and optimization based on swarm and evolutionary computation
- Author
-
Aimin Zhou, A. K. Qin, Linqiang Pan, and Maoguo Gong
- Subjects
General Computer Science ,business.industry ,Computer science ,General Mathematics ,Swarm behaviour ,Collaborative learning ,Artificial intelligence ,business ,Evolutionary computation - Published
- 2019
27. Computational efficiency and universality of timed P systems with active membranes
- Author
-
Linqiang Pan and Bosheng Song
- Subjects
Computational model ,Theoretical computer science ,Correctness ,Computable function ,General Computer Science ,Unit of time ,Existential quantification ,Membrane computing ,Algorithm ,P system ,Theoretical Computer Science ,Mathematics ,Universality (dynamical systems) - Abstract
P systems are a class of computational models inspired by the structure and the functioning of a living cell. In the semantics of P systems, there exists a global clock, which marks the time for the system, and the execution time of each rule takes exactly one time unit. However, in living cells, the execution time of different biochemical reactions is dependent on many uncontrollable factors, and it is hard to know precisely the specific execution time of a reaction. In this work, with this biological inspiration, we consider the class of P systems with active membranes that are "robust" against the execution time of rules. Specifically, we give a time-free uniform solution to the SAT problem using P systems with active membranes, where the constructed P system can solve a family of instances with an arbitrarily given size, and the execution time of the involved rules has no influence on the correctness of the solution. We also prove that any Turing computable set of numbers can be generated by a time-free P system with active membranes in the sense that the set of numbers generated by the given P system with active membranes does not depend on the execution time of rules.
- Published
- 2015
28. A radial space division based evolutionary algorithm for many-objective optimization
- Author
-
Cheng He, Xingyi Zhang, Yaochu Jin, Linqiang Pan, and Ye Tian
- Subjects
0209 industrial biotechnology ,Mathematical optimization ,education.field_of_study ,Population ,Evolutionary algorithm ,02 engineering and technology ,Division (mathematics) ,Grid ,020901 industrial engineering & automation ,Local optimum ,Convergence (routing) ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,020201 artificial intelligence & image processing ,Focus (optics) ,education ,Software ,Mathematics - Abstract
In evolutionary many-objective optimization, diversity maintenance plays an important role in pushing the population towards the Pareto optimal front. Existing many-objective evolutionary algorithms mainly focus on convergence enhancement, but pay less attention to diversity enhancement, which may fail to obtain uniformly distributed solutions or fall into local optima. This paper proposes a radial space division based evolutionary algorithm for many-objective optimization, where the solutions in high-dimensional objective space are projected into the grid divided 2-dimensional radial space for diversity maintenance and convergence enhancement. Specifically, the diversity of the population is emphasized by selecting solutions from different grids, where an adaptive penalty based approach is proposed to select a better converged solution from the grid with multiple solutions for convergence enhancement. The proposed algorithm is compared with five state-of-the-art many-objective evolutionary algorithms on a variety of benchmark test problems. Experimental results demonstrate the competitiveness of the proposed algorithm in terms of both convergence enhancement and diversity maintenance.
- Published
- 2017
29. On languages generated by spiking neural P systems with weights
- Author
-
Xiangxiang Zeng, Xiangrong Liu, Lei Xu, and Linqiang Pan
- Subjects
Information Systems and Management ,Theoretical computer science ,Computer science ,business.industry ,Natural computing ,Foundation (engineering) ,Computer Science Applications ,Theoretical Computer Science ,Artificial Intelligence ,Control and Systems Engineering ,Natural science ,Christian ministry ,Artificial intelligence ,China ,business ,Membrane computing ,Software - Abstract
National Natural Science Foundation of China [61202011, 61272152, 61033003, 91130034, 61320106005]; Ph.D. Programs Foundation of Ministry of Education of China [20120121120039, 20120142130008]; Natural Science Foundation of Hubei Province [2011CDA027]
- Published
- 2014
30. Computational power of tissue P systems for generating control languages
- Author
-
Xingyi Zhang, Yanjun Liu, Linqiang Pan, and Bin Luo
- Subjects
Discrete mathematics ,Information Systems and Management ,Theoretical computer science ,Computation ,Model of computation ,Computer Science Applications ,Theoretical Computer Science ,Regular language ,Artificial Intelligence ,Control and Systems Engineering ,Alphabet ,Membrane computing ,Software ,P system ,Mathematics - Abstract
Tissue P systems are a class of distributed and parallel models of computation inspired by the way of communication among living cells or between cells and their environment. In this work, we investigate the computational power of tissue P systems, where each rule is assigned either with a label chosen from an alphabet or with the empty label λ . The sequence of labels of rules applied during a halting computation is defined as the result of the computation, and the set of all results computed by a given tissue P system is called a control language. We prove that tissue P systems with antiport rules of weight one and without symport rules characterize regular languages; tissue P systems with antiport rules of weight at most two (resp., symport rules of weight at most two) without symport rules (resp., antiport rules) are universal. Tissue P systems with antiport rules of weight one and symport rules of weight one are also proved to be universal. These results show that the rule complexity is crucial for tissue P systems to achieve a desired computational power.
- Published
- 2014
31. Spiking neural P systems with rules on synapses
- Author
-
Linqiang Pan, Gheorghe Pun, and Tao Song
- Subjects
Spiking neural network ,Computer Science::Emerging Technologies ,Theoretical computer science ,Quantitative Biology::Neurons and Cognition ,General Computer Science ,Completeness (order theory) ,Process information ,Membrane computing ,P system ,Theoretical Computer Science ,Mathematics - Abstract
Spiking neural P systems (SN P systems, for short) are a class of membrane systems inspired from the way the neurons process information and communicate by means of spikes. In this paper, we introduce and investigate a new class of SN P systems, with spiking rules placed on synapses. The computational completeness is first proved, then two small universal SN P systems with rules on synapses for computing functions are constructed. Specifically, when using standard spiking rules, we obtain a universal system with 39 neurons, while when using extended spiking rules on synapses, a universal SN P system with 30 neurons is constructed.
- Published
- 2014
32. Time-free solution to SAT problem using P systems with active membranes
- Author
-
Linqiang Pan, Tao Song, Luis F. Macías-Ramos, and Mario J. Pérez-Jiménez
- Subjects
Theoretical computer science ,Correctness ,General Computer Science ,Unit of time ,Computation ,Synchronizing ,Time complexity ,Algorithm ,Membrane computing ,P system ,Theoretical Computer Science ,Power (physics) ,Mathematics - Abstract
P systems are a class of distributed and parallel computation models inspired by the structure and the functioning of living cells. P systems have been used to solve computation hard problems, where the execution of each rule is completed in unit time (a global clock is assumed for timing and synchronizing the execution of rules). The assumption that the execution of each rule takes exactly one time unit plays an vital role to make a system working synchronously, and it has also been used to characterize the computational efficiency and time complexity of a system. In this work, we investigate the computation power of P systems without such time assumption. Specifically, we give a time-free solution to SAT problem using P systems with active membranes in the sense that the correctness of the solution does not depend on the precise timing of the involved rules.
- Published
- 2014
33. Array P systems with permitting features
- Author
-
K. G. Subramanian, Pradeep Isawasan, Linqiang Pan, Atulya K. Nagar, and Ibrahim Venkat
- Subjects
Reduction (complexity) ,Theoretical computer science ,General Computer Science ,Computer science ,Modeling and Simulation ,Feature (machine learning) ,Array data structure ,Algorithm ,Picture language ,Membrane computing ,P system ,Theoretical Computer Science - Abstract
The biologically inspired model, known as P system, has proved to be a general framework for investigating several problems related to computing in different fields. Two-dimensional picture array languages is one such area in which different kinds of P systems have been constructed for picture array generation. Incorporating the feature of permitting symbols in the rules, a new variety of array P system is constructed here for generating picture languages consisting of picture arrays. The advantage of this approach is that there is a reduction in the number of membranes used in the construction, in comparison to the existing array P system models.
- Published
- 2014
34. Universality of sequential spiking neural P systems based on minimum spike number
- Author
-
Keqin Jiang, Linqiang Pan, and Tao Song
- Subjects
Spiking neural network ,Discrete mathematics ,Forgetting ,General Computer Science ,Computation ,Random neural network ,Theoretical Computer Science ,Universality (dynamical systems) ,medicine.anatomical_structure ,medicine ,Neuron ,Membrane computing ,Algorithm ,Mathematics - Abstract
Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. Each neuron can have several spiking rules and forgetting rules and neurons work in parallel in the sense that each neuron that can fire should fire at each computation step. In this work, we consider SN P systems working in the sequential way, where the sequentiality is induced by the minimum number of spikes: at each step, one (resp. all) of the neurons with the minimum number of spikes among the neurons that are active (can fire) will fire, called min-sequentiality (resp. min-pseudo-sequentiality). We prove that SN P systems working in min-sequentiality or min-pseudo-sequentiality are universal as both number generating and accepting devices, where the computation results are encoded by the time elapsed between the first two spikes of the output neuron. The results give positive answers to two open problems formulated in [O.H. Ibarra, A. Paun, A. Rodriguez-Paton, Sequential SNP systems based on min/max spike number, Theoretical Computer Science 410 (30-32) (2009) 2982-2991].
- Published
- 2013
35. Asynchronous spiking neural P systems with local synchronization
- Author
-
Linqiang Pan, Tao Song, Gheorghe Pun, Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla. TIC193: Computación Natural, and Junta de Andalucía
- Subjects
Information Systems and Management ,Theoretical computer science ,Quantitative Biology::Neurons and Cognition ,Computer science ,Computation ,Synchronization ,Computer Science Applications ,Theoretical Computer Science ,symbols.namesake ,Turing machine ,Turing completeness ,Artificial Intelligence ,Control and Systems Engineering ,Asynchronous communication ,Bounded function ,symbols ,Bio-inspired computing ,Software - Abstract
Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. Asynchronous SN P systems are non-synchronized systems, where the use of spiking rules (even if they are enabled by the contents of neurons) is not obligatory. It remains open whether asynchronous SN P systems with standard spiking rules are equivalent with Turing machines. In this paper, with a biological inspiration (in order to achieve some specific biological functioning, neurons from the same functioning motif or community work synchronously to cooperate with each other), we introduce the notion of local synchronization into asynchronous SN P systems. The computation power of asynchronous SN P systems with local synchronization is investigated. Such systems consisting of general neurons (respectively, unbounded neurons) and using standard spiking rules are proved to be universal. Asynchronous SN P systems with local synchronization consisting of bounded neurons and using standard spiking rules characterize the semilinear sets of natural numbers. These results show that the local synchronization is useful, it provides some ''programming capacity'' useful for achieving a desired computation power.
- Published
- 2013
36. Sequential spiking neural P systems with exhaustive use of rules
- Author
-
Bin Luo, Xianyong Fang, Xingyi Zhang, and Linqiang Pan
- Subjects
Neurons ,Statistics and Probability ,Class (set theory) ,Theoretical computer science ,Parallelism (rhetoric) ,Systems Biology ,Applied Mathematics ,Computation ,Models, Neurological ,Action Potentials ,General Medicine ,Turing computability ,General Biochemistry, Genetics and Molecular Biology ,Power (physics) ,Modeling and Simulation ,Computer Simulation ,Neural Networks, Computer ,Membrane computing ,Algorithm ,Mathematics ,Register machine - Abstract
Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes, where neurons work in parallel in the sense that each neuron that can fire should fire, but the work in each neuron is sequential in the sense that at most one rule can be applied at each computation step. In this work, we consider SN P systems with the restriction that at most one neuron can fire at each step, and each neuron works in an exhaustive manner (a kind of local parallelism – an applicable rule in a neuron is used as many times as possible). Such SN P systems are called sequential SN P systems with exhaustive use of rules. The computation power of sequential SN P systems with exhaustive use of rules is investigated. Specifically, characterizations of Turing computability and of semilinear sets of numbers are obtained, as well as a strict superclass of semilinear sets is generated. The results show that the computation power of sequential SN P systems with exhaustive use of rules is closely related with the types of spiking rules in neurons.
- Published
- 2012
37. A weakly universal spiking neural P system
- Author
-
Linqiang Pan, Xiangxiang Zeng, and Chun Lu
- Subjects
Spiking neural network ,Theoretical computer science ,Artificial neural network ,Quantitative Biology::Neurons and Cognition ,Computer science ,business.industry ,Directed graph ,ComputerSystemsOrganization_PROCESSORARCHITECTURES ,Universality (dynamical systems) ,Computer Science Applications ,Modeling and Simulation ,Modelling and Simulation ,Artificial intelligence ,business ,Membrane computing ,P system ,Register machine - Abstract
Looking for small universal computing devices is a natural and well investigated topic in computer science. Recently, this topic was also investigated in the framework of spiking neural P systems. One of the small universality results is that a small weakly universal extended spiking neural P system with 12 neurons was constructed. In this paper, a new way is introduced for simulating register machines by spiking neural P systems, where only one neuron is used for all instructions of the register machine; in this way, we can use less neurons to construct universal spiking neural P system. Specifically, we give a smaller weakly universal spiking neural P system that uses extended rules and has only 9 neurons.
- Published
- 2010
- Full Text
- View/download PDF
38. A P system model with pure context-free rules for picture array generation
- Author
-
Linqiang Pan, Atulya K. Nagar, See Keong Lee, and K. G. Subramanian
- Subjects
Grammar ,business.industry ,Computer science ,media_common.quotation_subject ,Context (language use) ,Computer Science Applications ,Variety (cybernetics) ,Modeling and Simulation ,Rewriting ,Artificial intelligence ,business ,Membrane computing ,P system ,Generative power ,media_common - Abstract
Syntactic models constitute one of the main areas of mathematical studies on picture array generation. A number of 2D grammar models have been proposed motivated by a variety of applications. A P system is a biologically motivated new computing model, proposed by Paun in the area of membrane computing. It is a rich framework for dealing with different problems, including the problem of handling picture array generation. In this paper, the generative power of the array-rewriting P system with pure 2D context-free rules is investigated by comparing it with other 2D grammar models, thus bringing out the suitability of this P system model for picture array generation.
- Published
- 2010
39. Computational complexity of tissue-like P systems
- Author
-
Mario J. Pérez-Jiménez and Linqiang Pan
- Subjects
Tissue P systems ,Statistics and Probability ,Class (set theory) ,Numerical Analysis ,Theoretical computer science ,Algebra and Number Theory ,Control and Optimization ,Computational complexity theory ,Cell separation ,Computer science ,General Mathematics ,Applied Mathematics ,P versus NP problem ,Theoretical models ,Workspace ,Membrane computing ,Feature (machine learning) ,SAT ,Algorithm - Abstract
Membrane systems, also called P systems, are biologically inspired theoretical models of distributed and parallel computing. This paper presents a new class of tissue-like P systems with cell separation, a feature which allows the generation of new workspace. We study the efficiency of the class of P systems and draw a conclusion that only tractable problems can be efficiently solved by using cell separation and communication rules with the length of at most 1. We further present an efficient (uniform) solution to SAT by using cell separation and communication rules with length at most 6. We conclude that a borderline between efficiency and non-efficiency exists in terms of the length of communication rules (assuming P≠NP). We discuss future research topics and open problems.
- Published
- 2010
- Full Text
- View/download PDF
40. Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources
- Author
-
Alberto Leporati, Linqiang Pan, Tseren-Onolt Ishdorj, Xingyi Zhang, Xiangxiang Zeng, Ishdorj, T, Leporati, A, Pan, L, Zeng, X, and Zhang, X
- Subjects
Discrete mathematics ,General Computer Science ,Spiking neural P systems, QSAT, Q3SAT, Pre-computed resources ,QSAT ,Q3SAT ,INF/01 - INFORMATICA ,Computer Science::Computational Complexity ,Theoretical Computer Science ,Exponential function ,Resource (project management) ,Spiking neural P systems ,PSPACE-complete problems ,Boolean data type ,Time complexity ,Computer Science(all) ,PSPACE ,Mathematics - Abstract
In this paper we continue previous studies on the computational effciency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.
- Published
- 2010
41. Spiking neural P systems: An improved normal form
- Author
-
Gheorghe Paun and Linqiang Pan
- Subjects
Discrete mathematics ,Spiking neural P system ,Forgetting ,Quantitative Biology::Neurons and Cognition ,General Computer Science ,Semilinear set ,Computability ,Turing computability ,Universality (dynamical systems) ,Theoretical Computer Science ,Turing machine ,symbols.namesake ,symbols ,Membrane computing ,Arithmetic function ,Regular expression ,Finite set ,Mathematics ,Computer Science(all) - Abstract
Spiking neural P systems (in short, SN P systems) are computing devices based on the way the neurons communicate through electrical impulses (spikes). These systems involve various ingredients; among them, we mention forgetting rules and the delay in firing rules. However, it is known that the universality can be obtained without using these two features. In this paper we improve this result in two respects: (i) each neuron contains at most two rules (which is optimal for systems used in the generative mode), and (ii) the rules in the neurons using two rules have the same regular expression which controls their firing. This result answers a problem left open in the literature, and, in this context, an incompleteness in some previous proofs related to the elimination of forgetting rules is removed. Moreover, this result shows a somewhat surprising uniformity of the neurons in the SN P systems able to simulate Turing machines, which is both of a theoretical interest and it seems to correspond to a biological reality. When a bound is imposed on the number of spikes present in a neuron at any step of a computation (such SN P systems are called finite), two surprising results are obtained. First, a characterization of finite sets of numbers is obtained in the generative case (this contrasts the case of other classes of SN P systems, where characterizations of semilinear sets of numbers are obtained for finite SN P systems). Second, the accepting case is strictly more powerful than the generative one: all finite sets and also certain arithmetical progressions can be accepted. A precise characterization of the power of accepting finite SN P systems without forgetting rules and delay remains to be found.
- Published
- 2010
- Full Text
- View/download PDF
42. On languages generated by asynchronous spiking neural P systems
- Author
-
Xingyi Zhang, Xiangxiang Zeng, and Linqiang Pan
- Subjects
Theoretical computer science ,Quantitative Biology::Neurons and Cognition ,General Computer Science ,Computer Science::Neural and Evolutionary Computation ,Universality (philosophy) ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Characterization (mathematics) ,Universality ,Theoretical Computer Science ,Recursively enumerable language ,Register machines ,Spiking neural P systems ,Asynchronous communication ,Membrane computing ,Computer Science::Programming Languages ,Computer Science(all) ,Mathematics - Abstract
In this paper, we investigate the languages generated by asynchronous spiking neural P systems. Characterizations of finite languages and recursively enumerable languages are obtained by asynchronous spiking neural P systems with extended rules. The relationships of the languages generated by asynchronous spiking neural P systems with regular and non-semilinear languages are also investigated.
- Published
- 2009
43. Some three-color Ramsey numbers, R(P4,P5,Ck) and R(P4,P6,Ck)
- Author
-
Xiaodong Xu, Xiaolong Shi, Zehui Shao, and Linqiang Pan
- Subjects
Combinatorics ,Discrete mathematics ,Integer ,Colored ,Complete graph ,Discrete Mathematics and Combinatorics ,Ramsey's theorem ,Mathematics - Abstract
For given graphs G"1,G"2,G"3, the three-color Ramsey number R(G"1,G"2,G"3) is defined to be the least positive integer n such that every 3-coloring of the edges of complete graph K"n contains a monochromatic copy of G"i colored with i, for some [email protected][email protected]?3. In this paper, we prove that R(P"4,P"5,C"3)=11, R(P"4,P"5,C"4)=7, R(P"4,P"5,C"5)=11, R(P"4,P"5,C"7)=11, R(P"4,P"5,C"k)=k+2 for k>=23; R(P"4,P"6,C"4)=8, R(P"4,P"6,C"3)=R(P"4,P"6,C"5)=R(P"4,P"6,C"7)=13, R(P"4,P"6,C"k)=k+3 for k>=18.
- Published
- 2009
44. A DNA sticker algorithm for bit-substitution in a block cipher
- Author
-
Jin Xu, Linqiang Pan, and Xiutang Geng
- Subjects
CBC-MAC ,Computer Networks and Communications ,Computer science ,Computation ,Substitution (logic) ,Pseudorandom binary sequence ,Theoretical Computer Science ,law.invention ,Artificial Intelligence ,Hardware and Architecture ,DNA computing ,law ,Key (cryptography) ,Cryptanalysis ,Algorithm ,Software ,Block cipher - Abstract
To attack block cipher systems, it is inevitable to handle the bit-substitutions, such as S-box, cycle left shift, and expansion substitutions. In this paper, a DNA sticker algorithm for bit-substitution such as cycle left shift is proposed. The proposed algorithm requires two equal long memory strands. The first memory strand stores the original binary string, while the second memory strand stores the resulting binary string. With the proposed algorithm, cycle left shift is performed on a mass of equal long binary strings, and the computation complexity of the cycle left shift is O(n) for all n-bit binary strings. Furthermore, this work indicates that block cipher systems with a 64-bit key are perhaps insecure. This paper presents clear evidence of the ability of DNA computing to perform intractable computation problems.
- Published
- 2008
45. Improved taboo search algorithm for designing DNA sequences
- Author
-
Linqiang Pan, Xiutang Geng, Jianhua Xiao, Kai Zhang, and Jin Xu
- Subjects
media_common.quotation_subject ,Taboo ,DNA sequencing ,law.invention ,Set (abstract data type) ,Important research ,DNA computing ,law ,Search algorithm ,General Materials Science ,General ,Algorithm ,Mathematics ,media_common - Abstract
The design of DNA sequences is one of the most practical and important research topics in DNA computing. We adopt taboo search algorithm and improve the method for the systematic design of equal-length DNA sequences, which can satisfy certain combinatorial and thermodynamic constraints. Using taboo search algorithm, our method can avoid trapping into local optimization and can find a set of good DNA sequences satisfying required constraints.
- Published
- 2008
46. A simple simulated annealing algorithm for the maximum clique problem
- Author
-
Jianhua Xiao, Xiutang Geng, Jin Xu, and Linqiang Pan
- Subjects
Clique ,Trust region ,Mathematical optimization ,Information Systems and Management ,Optimization problem ,Adaptive simulated annealing ,Computer Science Applications ,Theoretical Computer Science ,Clique problem ,Artificial Intelligence ,Control and Systems Engineering ,Simple (abstract algebra) ,Simulated annealing ,Software ,Mathematics - Abstract
Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.
- Published
- 2007
47. Further remark on P systems with active membranes and two polarizations
- Author
-
Carlos Martín-Vide and Linqiang Pan
- Subjects
Discrete mathematics ,Computer Networks and Communications ,Computer science ,Open problem ,Computability ,Parallel algorithm ,Constraint satisfaction ,Theoretical Computer Science ,Decidability ,Combinatorics ,Turing machine ,symbols.namesake ,Membrane ,Artificial Intelligence ,Hardware and Architecture ,symbols ,Boolean satisfiability problem ,Membrane computing ,Time complexity ,Software - Abstract
P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type. In this paper, some restrictions on the general form of the developing rules are considered, under which it is still possible to solve NP-complete problems. We present an algorithm for deterministically deciding SAT in linear time by P systems with active membranes using two polarizations and rules of restricted versions of types (a), (c), (e). The result obtained in this paper answered an open problem proposed by Alhazov and Freund in the aspect of computing efficiency.
- Published
- 2006
48. Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes
- Author
-
Linqiang Pan and Carlos Martín-Vide
- Subjects
Mathematical optimization ,Computer Networks and Communications ,Membrane algorithm ,Computer science ,Continuous knapsack problem ,Parallel algorithm ,Theoretical Computer Science ,Artificial Intelligence ,Hardware and Architecture ,Cutting stock problem ,Knapsack problem ,NP-complete ,Algorithm ,Membrane computing ,Integer programming ,Time complexity ,Software - Abstract
P systems are parallel molecular computing models based on pro- cessing multisets of objects in cell-like membrane structures. In this paper we give a membrane algorithm to multidimensional 0-1 knapsack problem in lin- ear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modi¯ed to solve general 0-1 integer programming problem.
- Published
- 2005
49. LOCALIZATION THEOREM ON HAMILTONIAN GRAPHS
- Author
-
Linqiang Pan, Kemin Zhang, and Guofei Zhou
- Subjects
Physics ,Combinatorics ,General Mathematics ,Localization theorem ,Induced subgraph ,General Physics and Astronomy ,Hamiltonian graphs ,Graph - Abstract
Let G be a 2-connected graph of order n(= 3). If I(u, v) = S(u, v) or max {d(u), d(v)} = n/2 for any two vertices u, v at distance two in an induced subgraph K1,3 or P3 of G, then G is hamiltonian. Here I(u, v) = |N(u) ∩ N(v)|, S(u, v) denotes the number of edges of maximum star containing u, v as an induced subgraph in G.
- Published
- 2000
50. Preface
- Author
-
Linqiang Pan and Guangzhao Cui
- Subjects
Computational Mathematics ,Computational Theory and Mathematics ,Modeling and Simulation ,Modelling and Simulation - Published
- 2009
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.