Abstract
In this work we propose an efficient solution to calculate the minimum editing distance between membrane structures of arbitrary P systems. We use a new model of tree automata based on multisets of states and symbols linked to the finite control. This new model accepts a set of trees with symmetries between their internal nodes (mirrored trees). Once we have calculated the editing distance between an arbitrary tree and an arbitrary multiset tree automaton, we can translate the classical operations of insertion, deletion and substitution into rule applications of membrane dissolving and membrane creation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alhazov, A., Ishdorj, T.O.: Membrane operations in P systems with active membranes. In: Păun, G., Riscos-Núñez, A., Romero-Jiménez, A., Sancho Caparrini, F. (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, TR 01/04 of RGNC, Sevilla University, pp. 37–844 (2004)
Calude, C., Păun, G., Rozenberg, G., Salomaa, A.: Multiset Processing. Mathematical, Computer Science, Molecular Computing Points of View, LNCS, vol. 2235. Springer, Heidelberg (2001)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1997), Available on http://www.grappa.univ-lille3.fr/tata
Csuhaj-Varjú, E., Di Nola, A., Păun, G., Pérez-Jiménez, M., Vaszil, G.: Editing configurations of P systems. In: Proc. Third Brainstorming Week on Membrane Computing, RGNC Report 01/2005, Sevilla, pp. 131–155 (2005)
Csuhaj-Varjú, E., Martín-Vide, C., Mitrana, V.: Multiset automata. In: [2], pp. 69–83
Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2), 248–264 (1972)
Freund, R., Oswald, M., Păun, A.: P systems generating trees. In: Mauri, G., Păun, G., Zandron, C. (eds.) Pre-proceedings of Fifth Workshop on Membrane Computing, WMC5, Milano, June 2004, MolCoNet project IST-2001-32008, pp. 221–232 (2004)
Gécseg, F., Steinby, M.: Tree languages. In: vol. 3 of [15], pp.1–69
Kudlek, M., Martín-Vide, C., Păun, G.: Towards a formal macroset theory. In: [2], pp. 123–133
López, D., Sempere, J.M., García, P.: Error correcting analysis for tree languages. International Journal of Pattern Recognition and Artificial Intelligence 14(3), 357–368 (2000)
Păun, A.: On P systems with active membranes. In: Proceedings of Conference on Unconventionals Models of Computation, Brussels, pp. 187–201 (2000)
Păun, G.: Membrane Computing. An Introduction. Springer, Berlin (2002)
Păun, G., Suzuki, Y., Tanaka, H., Yokomori, T.: On the power of membrane division in P systems. Theoretical Computer Sci. 324(1), 61–85 (2004)
Rivest, R.L., Cormen, T.H., Leiserson, C.E., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill (2001)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer, Berlin (1997)
Sempere, J.M., López, D.: Recognizing membrane structures with tree automata. In: Gutiérrez Naranjo, M.A., Riscos-Núñez, A., Romero-Campero, F.J., Sburlan, D. (eds.) Proceedings of the 3rd Brainstorming Week on Membrane Computing 2005, RGNC Report 01/2005 Research Group on Natural Computing, Sevilla University, pp. 305–316. Fénix Editora (2005)
Syropoulos, A.: Mathematics of multisets. In: [2], pp. 347–358
Zhang, K.: A constrained edit distance between unordered labelled trees. Algorithmica 15, 205–222 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
López, D., Sempere, J.M. (2006). Editing Distances Between Membrane Structures. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2005. Lecture Notes in Computer Science, vol 3850. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11603047_22
Download citation
DOI: https://doi.org/10.1007/11603047_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30948-2
Online ISBN: 978-3-540-32340-2
eBook Packages: Computer ScienceComputer Science (R0)