×
Christinal, Hepzibah A.; Díaz-Pernil, Daniel; Real, Pedro

P systems and computational algebraic topology. (English) Zbl 1207.68137

Math. Comput. Modelling 52, No. 11-12, 1982-1996 (2010).
Summary: Membrane Computing is a paradigm inspired from biological cellular communication. Membrane computing devices are called P systems. In this paper we calculate some algebraic-topological information of 2D and 3D images in a general and parallel manner using P systems. First, we present a new way to obtain the homology groups of 2D digital images in time logarithmic with respect to the input data involving an improvement with respect to the algorithms development by S. Peltier et al. Second, we obtain an edge-segmentation of 2D and 3D digital images in constant time with respect to the input data.

Cited in 5 Documents

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
55P99 Homotopy theory
92B05 General biology and biomathematics

Keywords:

P systems; membrane computing; homology groups; segmentation; digital topology; algebraic topology
Cite Review PDF
Full Text: DOI Link

References:

[1] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI · Zbl 0317.68006
[2] McCulloch, W. S.; Pitts, W., A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics, 5, 115-133 (1943) · Zbl 0063.03860
[3] Head, T., Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors, Bulletin of Mathematical Biology, 49, 737-759 (1987) · Zbl 0655.92008
[4] Adleman, L. M., Molecular computations of solutions to combinatorial problems, Science, 226, 1021-1024 (1994)
[5] Păun, Gh., Membrane Computing. An Introduction (2002), Springer-Verlag: Springer-Verlag Berlin · Zbl 1034.68037
[6] Alberts, B.; Johnson, A.; Lewis, J.; Raff, M.; Roberts, K.; Walter, P., Molecular Biology of the Cell (2002), Garland Science
[7] Păun, Gh., Computing with membranes, Journal of Computer and System Sciences, 61, 1, 108-143 (2000) · Zbl 0956.68055
[8] Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., A fast P system for finding a balanced 2-partition, Soft Computing, 9, 9, 673-678 (2005) · Zbl 1101.68581
[9] Díaz-Pernil, D.; Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., A logarithmic bound for solving Subset Sum with P systems, (Lecture Notes in Computer Science, vol. 4860 (2007)), 257-270 · Zbl 1137.68384
[10] Martín-Vide, C.; Pazos, J.; Păun, Gh.; Rodríguez Patón, A., Tissue P systems, Theoretical Computer Science, 296, 295-326 (2003) · Zbl 1045.68063
[11] Gh. Păun, M.J. Pérez-Jiménez, A. Riscos-Núñez, Tissue P System with cell division. Second Brainstorming Week on Membrane Computing, Sevilla, Report RGNC 01/2004, (2004), pp. 380-386.; Gh. Păun, M.J. Pérez-Jiménez, A. Riscos-Núñez, Tissue P System with cell division. Second Brainstorming Week on Membrane Computing, Sevilla, Report RGNC 01/2004, (2004), pp. 380-386.
[12] Díaz-Pernil, D.; Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., A linear time solution to the partition problem in a cellular tissue-like model, Journal of Computational and Theoretical Nanoscience, 5, 7, 884-889 (2010)
[13] Díaz-Pernil, D.; Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., Solving Subset Sum in linear time by using tissue P systems with cell division, (Mira, J.; Alvarez, J. R., Bio-inspired Modeling of Cognitive Tasks. Bio-inspired Modeling of Cognitive Tasks, Lecture Notes in Computer Science, vol. 4527 (2007)), 170-179
[14] Díaz-Pernil, D.; Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., A uniform family of tissue P systems with cell division solving 3-COL in a linear time, Theoretical Computer Science, 404, 1-2, 76-87 (2008) · Zbl 1151.68016
[15] J. Chao, J. Nakayama, Cubical singular simples model for 3D objects and fast computation of homology groups, in: Proc. ICPR’96, IEEE, 1996, pp. 190-194.; J. Chao, J. Nakayama, Cubical singular simples model for 3D objects and fast computation of homology groups, in: Proc. ICPR’96, IEEE, 1996, pp. 190-194.
[16] Ceterchi, R.; Madhu, M.; Paun, G.; Subramanian, K. G., Array-rewriting P systems, Natural Computing, 2, 229-249 (2003) · Zbl 1048.68045
[17] P.H. Chandra, K.G. Subramanian, On picture arrays generated by P systems, in: R. Freund, G. Lojka, M. Oswald, Gh. Paun (Eds.) Pre-Proc. of Sixth International Workshop on Membrane Computing, WMC6, Vienna, June 18-21, 2005, pp. 282-288.; P.H. Chandra, K.G. Subramanian, On picture arrays generated by P systems, in: R. Freund, G. Lojka, M. Oswald, Gh. Paun (Eds.) Pre-Proc. of Sixth International Workshop on Membrane Computing, WMC6, Vienna, June 18-21, 2005, pp. 282-288.
[18] Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Romero-Campero, F. J., A linear solution for QSAT with Membrane Creation, (Lecture Notes in Computer Science, vol. 3850 (2006)), 241-252 · Zbl 1135.68411
[19] Păun, Gh., Computing with membranes: attacking NP-complete problems, (Antoniou, I.; Calude, C.; Dinneen, M. J., In Unconventional Models of Computation. In Unconventional Models of Computation, UMC’2K (2000)), 94-115 · Zbl 0967.68065
[20] Hatcher, A., Algebraic Topology (2001), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK
[21] González-Díaz, R.; Real, P., On the cohomology of 3D digital images, Discrete Applied Mathematics, 147, 245-263 (2005) · Zbl 1099.68120
[22] González-Díaz, R.; Medrano, B.; Real, P.; Sánchez, J., (Reusing Integer Homology Information of Binary Digital Images. Reusing Integer Homology Information of Binary Digital Images, Lecture Notes in Computer Science, vol. 4245 (2006)), 199-210 · Zbl 1136.68575
[23] Molina-Abril, H.; Real, P., (Advanced Homological Information on 3D Digital volumes. Advanced Homological Information on 3D Digital volumes, Lecture Notes in Computer Science, vol. 5342 (2008)), 361-371
[24] Real, P.; Molina-Abril, H.; Kropatsch, W., Homological tree-based strategies for image analysis, (Computer Analysis and Image Patterns, CAIP (2009))
[25] González-Díaz, R.; Real, P., Computation of cohomology operations of finite simplicial complexes, Homology Homotopy and Applications, 2, 83-93 (2003) · Zbl 1028.55011
[26] González-Díaz, R.; Real, P., (Towards Digital Cohomology. Towards Digital Cohomology, Lecture Notes in Computer Science, vol. 2886 (2003)), 92-101 · Zbl 1254.68303
[27] González-Díaz, R.; Medrano, B.; Real, P.; Sanchez-Pelaez, J., (Algebraic Topological Analysis of Time-sequence of Digital Images. Algebraic Topological Analysis of Time-sequence of Digital Images, Lecture Notes in Computer Science, vol. 3718 (2005)), 208-219 · Zbl 1169.68642
[28] Real, P., An algorithm computing homotopy groups, Mathematics and Computers in Simulation, 42, 4-6, 461-465 (1996) · Zbl 1037.55502
[29] Real, P., Homological perturbation theory and associativity, (Homology, Homotopy and Applications (2000)), 51-88 · Zbl 0949.18005
[30] Sergeraert, F., The computability problem in algebraic topology, Advances in Mathematics, 104, 1-29 (1994) · Zbl 0823.55011
[31] Peltier, S.; Ion, A.; Haxhimusa, Y.; Kropatsch, W. G.; Damiand, G., Computing homology group generators of images using irregular graph pyramids, (Lecture Notes in Computer Science, vol. 4538 (2007)), 283-294 · Zbl 1182.68334
[32] Shapiro, Linda G.; Stockman, George C., Computer Vision (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.