Using membrane computing for effective homology. (English) Zbl 1253.68331
Summary: Effective homology is an algebraic-topological method based on the computational concept of chain homotopy equivalence on a cell complex. Using this algebraic data structure, effective homology gives answers to some important computability problems in algebraic topology. In a discrete context, effective homology can be seen as a combinatorial layer given by a forest graph structure spanning every cell of the complex. In this paper, by taking as input a pixel-based 2D binary object, we present a logarithmic-time uniform solution for describing a chain homotopy operator for its adjacency graph. This solution is based on membrane computing techniques applied to the spanning forest problem and it can be easily extended to higher dimensions.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 55U15 | Chain complexes in algebraic topology |
| 68P05 | Data structures |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
tissue-like P systems; membrane computing; effective homology; computational algebraic topology; digital topologyReferences:
| [1] | Ceterchi, R., Mutyam, M., Păun, G., Subramanian, K.G.: Array-rewriting P systems. Nat. Comput. 2(3), 229–249 (2003) · Zbl 1048.68045 · doi:10.1023/A:1025497107681 |
| [2] | Chao, J., Nakayama, J.: Cubical singular simplex model for 3D objects and fast computation of homology groups. In: 13th International Conference on Pattern Recognition (ICPR’96), vol. IV, pp. 190–194. IEEE Computer Society, IEEE Computer Society, Los Alamitos, CA, USA (1996) |
| [3] | Christinal, H.A., Díaz-Pernil, D., Real, P.: Segmentation in 2D and 3D image using tissue-like P system. In: Bayro-Corrochano, E., Eklundh, J.O. (eds.) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications 14th Iberoamerican Conference on Pattern Recognition, CIARP 2009, Guadalajara, Jalisco, Mexico, November 15–18, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5856, pp. 169–176. Springer, Berlin Heidelberg (2009) |
| [4] | Christinal, H.A., Díaz-Pernil, D., Real, P.: Using membrane computing for obtaining homology groups of binary 2D digital images. In: Wiederhold, P., Barneva, R.P. (eds.) Combinatorial Image Analysis 13th International Workshop, IWCIA 2009, Playa del Carmen, Mexico, November 24–27, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5852, pp. 383–396. Springer, Berlin Heidelberg (2009) · Zbl 1267.68283 |
| [5] | Christinal, H.A., Díaz-Pernil, D., Real, P.: P systems and computational algebraic topology. Math. Comput. Model. 52(11–12), 1982–1996 (2010) (The BIC-TA 2009 Special Issue. International Conference on Bio-Inspired Computing, Theory and Applications) · Zbl 1207.68137 |
| [6] | Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-Núñez, A.: A linear-time tissue P system based solution for the 3-coloring problem. Electron. Notes Theor. Comput. Sci. 171(2), 81–93 (2007) · Zbl 1277.68073 · doi:10.1016/j.entcs.2007.05.009 |
| [7] | 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. In: Mira, J., Álvarez, J.R. (eds.) IWINAC (1), Lecture Notes in Computer Science, vol. 4527, pp. 170–179. Springer, Berlin Heidelberg (2007) |
| [8] | Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Real, P., Sánchez-Canales, V.: Computing homology groups in binary 2D imagery by tissue-like P systems. Romanian J. Inf. Sci. Technol. 13(2), 141–152 (2010) |
| [9] | Eilenberg, S., MacLane, S.: Relations between homology and homotopy groups of spaces. Ann. Math. 46(3), pp. 480–509 (1945). http://www.jstor.org/stable/1969165 · Zbl 0061.40702 |
| [10] | Eilenberg, S., MacLane, S.: Relations between homology and homotopy groups of spaces. ii. Ann. Math. 51(3), pp. 514–533 (1950). http://www.jstor.org/stable/1969365 · Zbl 0036.12602 |
| [11] | González-Díaz, R., Jiménez, M.J., Medrano, B., Molina-Abril, H., Real, P.: Integral operators for computing homology generators at any dimension. In: Ruiz-Shulcloper, J., Kropatsch, W.G. (eds.) CIARP, Lecture Notes in Computer Science, vol. 5197, pp. 356–363. Springer, Berlin Heidelberg (2008) |
| [12] | González-Díaz, R., Jiménez, M.J., Medrano, B., Real, P.: Chain homotopies for object topological representations. Discret. Appl. Math. 157(3), 490–499 (2009) · Zbl 1168.68045 · doi:10.1016/j.dam.2008.05.029 |
| [13] | González-Díaz, R., Real, P.: On the cohomology of 3D digital images. Discret. Appl. Math. 147(2–3), 245–263 (2005). http://dx.doi.org/10.1016/j.dam.2004.09.014 · Zbl 1099.68120 |
| [14] | Kenmochi, Y., Imiya, A., Ichikawa, A.: Discrete combinatorial geometry. Pattern Recogn. 30(10), 1719–1728 (1997) · Zbl 0886.68118 · doi:10.1016/S0031-3203(97)00001-0 |
| [15] | Kenmochi, Y., Imiya, A., Ichikawa, A.: Boundary extraction of discrete objects. Comput. Vis. Image Underst. 71(3), 281–293 (1998) · doi:10.1006/cviu.1997.0652 |
| [16] | Martín-Vide, C., Păun, G., Pazos, J., Rodríguez-Patón, A.: Tissue P systems. Theor. Comput. Sci. 296(2), 295–326 (2003) · Zbl 1045.68063 · doi:10.1016/S0304-3975(02)00659-X |
| [17] | Molina-Abril, H., Real, P.: Advanced homology computation of digital volumes via cell complexes. In: da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J.T.Y., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) SSPR/SPR, Lecture Notes in Computer Science, vol. 5342, pp. 361–371. Springer, Berlin Heidelberg (2008) |
| [18] | Păun, A., Păun, G.: The power of communication: P systems with symport/antiport. New Gener. Comput. 20(3), 295–306 (2002) · Zbl 1024.68037 · doi:10.1007/BF03037362 |
| [19] | Păun, G.: Computing with membranes. Technical Report 208, Turku Centre for Computer Science, Turku, Finland (1998) |
| [20] | Păun, G.: Computing with membranes. J. Comput. Syst. Sci. 61(1), 108–143 (2000). http://dx.doi.org/10.1006/jcss.1999.1693 . See also [19] · Zbl 0956.68055 |
| [21] | Păun, G.: Membrane Computing. An Introduction. Springer, Berlin, Germany (2002) |
| [22] | Păun, G., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, England (2010) · Zbl 1237.68001 |
| [23] | Real, P.: Homological perturbation theory and associativity. Homol. Homotopy Appl. 2(5), 51–88 (2000) · Zbl 0949.18005 |
| [24] | Real, P., Molina-Abril, H.: Cell at-models for digital volumes. In: Torsello, A., Escolano, F., Brun, L. (eds.) GbRPR, Lecture Notes in Computer Science, vol. 5534, pp. 314–323. Springer, Berlin Heidelberg (2009) · Zbl 1248.68528 |
| [25] | Real, P., Molina-Abril, H., Kropatsch, W.G.: Homological tree-based strategies for image analysis. In: Jiang, X., Petkov, N. (eds.) CAIP, Lecture Notes in Computer Science, vol. 5702, pp. 326–333. Springer, Berlin Heidelberg (2009) |
| [26] | Sergeraert, F.: The computability problem in algebraic topology. Adv. Math. 104, 1–29 (1994) · Zbl 0823.55011 · doi:10.1006/aima.1994.1018 |
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.
