Top

Applicable Algebra in Engineering, Communication and Computing

Published in:

01-12-2012 | Original Paper

Using Membrane Computing for Effective Homology

Authors: Daniel Díaz-Pernil, Hepzibah A. Christinal, Miguel A. Gutiérrez-Naranjo, Pedro Real

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 5-6/2012

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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 \(\phi \) 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.

previous article Remarks on the generalized cyclotomic sequences of length

next article Torus square tilings

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

We refer to [21] for basic information in this area, to [22] for a comprehensive presentation and the web site http://ppage.psystems.eu for the up-to-date information.

The objects from \(\varGamma - \mathcal E \) placed in the environment along the computation are not explicitely showed in the configuration since they are not relevant in this approach.

Ceterchi, R., Mutyam, M., Păun, G., Subramanian, K.G.: Array-rewriting P systems. Nat. Comput. 2(3), 229–249 (2003)MathSciNetMATHCrossRef

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)

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)

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)

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)

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)CrossRef

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)

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)

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

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

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)MATHCrossRef

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

14.

Kenmochi, Y., Imiya, A., Ichikawa, A.: Discrete combinatorial geometry. Pattern Recogn. 30(10), 1719–1728 (1997)MATHCrossRef

15.

Kenmochi, Y., Imiya, A., Ichikawa, A.: Boundary extraction of discrete objects. Comput. Vis. Image Underst. 71(3), 281–293 (1998)CrossRef

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)MATHCrossRef

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)MATHCrossRef

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]

21.

Păun, G.: Membrane Computing. An Introduction. Springer, Berlin, Germany (2002)MATH

22.

Păun, G., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, England (2010)

23.

Real, P.: Homological perturbation theory and associativity. Homol. Homotopy Appl. 2(5), 51–88 (2000)MathSciNetMATH

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)

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)MathSciNetMATHCrossRef

Title: Using Membrane Computing for Effective Homology
Authors: Daniel Díaz-Pernil
Hepzibah A. Christinal
Miguel A. Gutiérrez-Naranjo
Pedro Real
Publication date: 01-12-2012
Publisher: Springer-Verlag
Published in: Applicable Algebra in Engineering, Communication and Computing / Issue 5-6/2012
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-012-0176-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Premium Partner