Editing Distances Between Membrane Structures

摘要

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.