The tree-to-tree editing problem

DOI10.1016/0020-0190(77)90064-3zbMath0391.68022OpenAlexW2048001624MaRDI QIDQ1251477

Stanley M. Selkow

Publication date: 1977

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(77)90064-3

zbMATH Keywords

Algorithmic Theory of MeasureEdit OperationsRecursive Algorithms

Mathematics Subject Classification ID

Trees (05C05) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (35)

Constrained tree editing ⋮ Statistical shape analysis of simplified neuronal trees ⋮ Algebraic dynamic programming on trees ⋮ Fuzzy trees in decision support systems ⋮ A similarity measure for graphs with low computational complexity ⋮ Tai mapping hierarchy for rooted labeled trees through common subforest ⋮ TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE ⋮ On the hardness of computing the edit distance of shallow trees ⋮ An inductive characterization of matching in binding bigraphs ⋮ Automated methods for the comparison of natural languages ⋮ Inexact tree pattern matching with 1-degree edit distance using finite automata ⋮ Good edit similarity learning by loss minimization ⋮ Recent advances in graph-based pattern recognition with applications in document analysis ⋮ A modified tree-to-tree correction problem ⋮ RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm. ⋮ Local similarity between quotiented ordered trees ⋮ Space efficient algorithms for ordered tree comparison ⋮ Learning probabilistic models of tree edit distance ⋮ Identifying approximately common substructures in trees based on a restricted edit distance ⋮ Fifty years of graph matching, network alignment and network comparison ⋮ Finding similar consensus between trees: An algorithm and a distance hierarchy ⋮ Selected tree classifier combination based on both accuracy and error diversity ⋮ Homeomorphic alignment of weighted trees ⋮ A survey on tree edit distance and related problems ⋮ Weighted edit distance computation: strings, trees, and Dyck ⋮ Sublinear DTD Validity ⋮ Some limit results for longest common subsequences ⋮ A new constrained edit distance between quotiented ordered trees ⋮ Homeomorphic Alignment of Edge-Weighted Trees ⋮ A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression. ⋮ Quantitative graph theory: a new branch of graph theory and network science ⋮ Computing a longest common subsequence for a set of strings ⋮ Decomposition algorithms for the tree edit distance problem ⋮ Matching of Bigraphs ⋮ New algorithms for the LCS problem

Cites Work

• Bounds for the String Editing Problem
• Bounds on the Complexity of the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• Matching Sequences under Deletion/Insertion Constraints

This page was built for publication: The tree-to-tree editing problem