Paper:

# Discrete Morse Theory Based Dynamic P Systems

## Jie Xue, Xiyu Liu, Wenxing Sun, and Shuo Yan

Shandong Normal University

East road of Wenhua, No.88, Jinan, Shandong 250014, China

This paper proposes a class of dynamic P systems with constraint of discrete Morse function (*DMD* P systems). Membrane structure is extended on complex. Rules control activities of membranes. New classes of rules and mechanism to change types of rules by discrete gradient vector field are provided as well. *DMD* P system extends P systems both in structures and rules. Solving air quality evaluation problem in linear time verifies the effectiveness of *DMD* P systems. Since air quality evaluation problem has significance in many areas. The new P systems provide an alternative for traditional membrane computing.

- [1] L. Pan and C. Martín-Vide, “Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes,” J. of Parallel and Distributed Computing, Vol.65, No.12, pp. 1578-1584, 2005.
- [2] T. Y. Nishida, “Membrane algorithms,” Lecture Notes in Computer Science, Vol.3850, pp. 55-66, 2005.
- [3] J. Zhao and N. Wang, “A bio-inspired algorithm based on membrane computing and its application to gasoline blending scheduling,” Computers and Chemical Engineering, Vol.35, pp. 272-283, 2011.
- [4] A. Kikuchi and T. Kawano, “Discrete Biochemistry of DNA: Arithmetic DNA Molecules for Binary Additions, Naturally Found Genetic Logic Circuits for Plant Sensing, and DNA-Based Animation,” J. Adv. Comput. Intell. Intell. Inform, Vol.20, No.5, pp. 671-680, 2016.
- [5] D. Díaz-Pernil, A. Berciano, F. Pena-Cantillana, and M. A. Gutiérrez-Naranjo, “Segmenting images with gradient-based edge detection using Membrane Computing,” Pattern Recognition Letters, Vol.34, pp. 846-855, 2013.
- [6] J. L. Shen, Y. M. Liu, and Y. L. Tzeng, “The Cluster-Weighted DEMATEL with ANP Method for Supplier Selection in Food Industry,” J. Adv. Comput. Intell. Intell. Inform, Vol.16, No.5, pp. 567-575, 2012.
- [7] D. Reid and M. Barrett-Baxendale, “Spatiotemporal Processing in a spiking neural P system,” Proc. of 2nd Int. Conf. on Developments in Systems Engineering, pp. 394-399, 2010.
- [8] G. Păun, “Computing with membranes,” J. of Computer and System Sciences, Vol.61, No.1, pp. 108-143, 2000.
- [9] C. Martín-Vide, J. Pazos, G. Păun, and A. Rodriguez-Paton, “Tissue P systems,” Theoretical Computer Science, Vol.296, No.2, pp. 295-326, 2003.
- [10] D. Díaz-Pernil, M. A. Gutiérrez-Naranjo, M. J. Pérez-Jiménez, and A. Riscos-Núñez, “A uniform family of tissue p systems with cell division solving 3-col in a linear time,” Theoretical Computer Science, Vol.404, No.1, pp. 76-87, 2008.
- [11] L. Pan and T. O. Ishdorj, “P systems with active membranes and separation rules,” J. of Universal Computer Science, Vol.10, No.5, pp. 630-649, 2004.
- [12] M. Ionescu, G. Păun, and T. Yokomori, “Spiking neural P systems,” Fundamenta Informaticae, Vol.71, No.2-3, pp. 279-308, 2006.
- [13] D. Sburlan, “P systems with chained rules,” Membrane Computing, pp. 359-370, Springer, 2012.
- [14] B. Song, L. Pan, and M. J. Pérez-Jiménez, “Tissue P Systems with Protein on Cells,” Fundamenta Informaticae, Vol.144, No.1, pp. 77-107, 2016.
- [15] J. Ming, J. Wang, K. Chen, H. Peng, and X. Song, “Tissue P System Combined with Producer/Consumer and Its Application in Micro-Grid Economic Operation,” J. of Computational and Theoretical Nanoscience, Vol.13, No.6, pp. 3936-3941, 2016.
- [16] B. Song and L. Pan, “A time-free uniform solution to subset sum problem by tissue P systems with cell division,” Mathematical Structures in Computer Science, Vol.27, No.1, pp. 17-32, 2017.
- [17] K. Jiang, W. Chen, Y. Zhang, and L. Pan, “Spiking neural P systems with homogeneous neurons and synapses,” Neurocomputing, Vol.171, pp. 1548-1555, 2016.
- [18] L. Pan, G. Păun, and B. Song, “Flat maximal parallelism in P systems with promoters,” Theoretical Computer Science, Vol.623, pp. 83-91, 2016.
- [19] T. Wu, Z. Zhang, G. Păun, and L. Pan, “On the Universality of Colored One-Catalyst P Systems,” Fundamenta Informaticae, Vol.144, No.2, pp. 205-212, 2016.
- [20] T. Song and L. Pan, “Spiking neural P systems with request rules,” Neurocomputing, Vol.193, pp. 193-200, 2016.
- [21] Z. Zhang, T. Wu, A. Păun, and L. Pan, “Numerical P systems with migrating variables,” Theoretical Computer Science, Vol.641, pp. 85-108, 2016.
- [22] K. G. Subramanian, P. Isawasan, I. Venkat, L. Pan, and A. Nagar, “Array P systems with permitting features,” J. of Computational Science, Vol.5, No.2, pp. 243-250, 2014.
- [23] A. P. Venkatesan, D. G. Thomas, T. Robinson, and A. Nagar, “Computing with membranes and picture arrays,” J. of Discrete Algorithms, Vol.33, pp. 31-42, 2015.
- [24] J. Xue and X. Liu, “Lattice based communication P systems with applications in cluster analysis,” Soft Computing, Vol.18, pp. 1425-1440, 2014.
- [25] L. Pan and G. Păun, “Spiking Neural P Systems with Anti-Spikes,” Int. J. of Computers, Communications & Control, Vol.4, No.3, pp. 273-282, 2009.
- [26] J. Wang, H. J. Hoogeboom, L. Pan, G. Păun, and M. J. Perez-Jiménez, “Spiking Neural P Systems with Weights,” Neural Computation, Vol.22, No.10, pp. 2615-2646, 2010.
- [27] L. Pan, X. Zeng, and X. Zhang, “Time-Free Spiking Neural P Systems,” Neural Computation, Vol.23, pp. 1320-1342, 2011.
- [28] T. Song, L. Pan, J. Wang, I. Venkat, K. G. Subramanian, and R. Abdullah, “Normal Forms of Spiking Neural P Systems With Anti-Spikes,” IEEE Trans. on Nanobioscience, Vol.11, No.4, pp. 352-360, 2012.
- [29] L. Pan and C. Martín-Vide, “Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes,” J. of Parallel and Distributed Computing, Vol.65, pp. 1578-1584, 2005.
- [30] A. Alhazov, C. Martín-Vide, and L. Pan, “Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes,” Fundamenta Informaticae, Vol.58, No.2, pp. 66-77, 2003.
- [31] T. O. Ishdorj, A. Leporati, L. Pan, X. Zeng, and X. Zhang, “Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources,” Theoretical Computer Science, Vol.411, pp. 2345-2358, 2010.
- [32] Z. Xingyi, W. Shuo, N. Yunyun, and P. Linqiang, “Tissue P systems with cell separation: attacking the partition problem,” Science China Information Sciences, Vol.54, No.2, pp. 293-304, 2011.
- [33] L. Pan, G. Păun, M. J. Pérez-Jiménez, “Spiking neural P systems with neuron division and budding,” Science China Information Sciences, Vol.54, No.8, pp. 1596-1607, 2011.
- [34] G. Păun, G. Rozenberg, and A. Salomaa, “Membrane Computing,” Oxford University Press, 2010.
- [35] F. Robin, “Morse theory for cell complexes,” Advances in Mathematics, Vol.134, No.1, pp. 90-145, 1998.
- [36] F. Robin, “Users guide to discreteMorse theory,” Seminaire Lotharingien de Combinatoire, Vol.48, article B48c, pp. 1-35, 2002.
- [37] X. Liu and A. Xue (J. Xue), “Communication P Systems on Simplicial Complexes with Applications in Cluster Analysis,” Discrete Dynamics in Nature and Society, No.12, pp. 715-735, 2012.
- [38] C. Qiansheng, “Attribute Recognition Theoretical Model With Application,” Act a Scientiar um Naturalium Universitatis Pekinensis, Vol.33, No.1, 1997.
- [39] L. Huiqing and Z. Xianqi, “Model Based on Coefficient of Entropy to Comprehensive Evaluating Air Quality,” Environmental Science & Technology, Vol.31, No.7, 2008.