In this article, we propose tree edit distance with variables, which is an extension of the tree edit distance to handle trees with variables and has a potential application to measuring the similarity between mathematical formulas, especially, those appearing in mathematical models of biological systems. We analyze the computational complexities of several variants of this new model. In particular, we show that the problem is NP-complete for ordered trees. We also show for unordered trees that the problem of deciding whether or not the distance is 0 is graph isomorphism complete but can be solved in polynomial time if the maximum outdegree of input trees is bounded by a constant. This distance model is then extended for measuring the difference/similarity between two systems of differential equations, for which results of preliminary computational experiments using biological models are provided.
翻译:在此文章中,我们提议与变量编辑树距离,这是树编辑距离的延伸,用于与变量一起处理树木,并有可能用于测量数学公式之间的相似性,特别是生物系统数学模型中出现的数学公式的相似性。我们分析了这个新模型的若干变量的计算复杂性。特别是,我们显示,定购树的计算问题已经完成。我们还向未定序树显示,确定距离0是否为图象异形的问题已经完成,但如果输入树的最大超出度与一个常数相连接,则可以在多数值时间内解决。然后扩展这一距离模型,以测量两个差异方程系统之间的差异/相似性,为此提供了使用生物模型进行的初步计算实验的结果。