The String-to-String Correction Problem
From MaRDI portal
Publication:4404425
DOI10.1145/321796.321811zbMath0278.68032OpenAlexW1970026646WikidataQ29011825 ScholiaQ29011825MaRDI QIDQ4404425
Michael J. Fischer, Robert A. Wagner
Publication date: 1974
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321796.321811
Related Items
A common basis for similarity measures involving two strings†, Insertion-deletion systems with substitutions I, Scattered Factor-Universality of Words, DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM, How hard is to compute the edit distance, Boyer-Moore approach to approximate string matching, On-Line Approximate String Searching Algorithms: Survey and Experimental Results, Categories, relations and dynamic programming, An Edit Distance Between Graph Correspondences, Longest common subsequences, Unnamed Item, A general framework for enumerating equivalence classes of solutions, Absent Subsequences in Words, A Linear-Time n 0.4 -Approximation for Longest Common Subsequence, Testing membership for timed automata, Volume formula and growth rates of the balls of strings under the edit distances, Quantum bounds for 2D-grid and Dyck language, Linear-space S-table algorithms for the longest common subsequence problem, MPClan: protocol suite for privacy-conscious computations, On the hardness of computing the edit distance of shallow trees, Computing longest Lyndon subsequences and longest common Lyndon subsequences, Extremal event graphs: a (stable) tool for analyzing noisy time series data, Automated methods for the comparison of natural languages, Unnamed Item, Unnamed Item, Unnamed Item, Quantum complexity for vector domination problem, Space-efficient STR-IC-LCS computation, Hypercubes and isometric words based on swap and mismatch distance, Methodology for analyzing bitstreams based on the use of the Damerau-Levenshtein distance and other metrics, Calcul de la distance par les sous-mots, Near-optimal algorithm to count occurrences of subsequences of a given length, Unnamed Item, Locating the vertices of a steiner tree in an arbitrary metric space, EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS, DICTIONARY LOOK-UP WITHIN SMALL EDIT DISTANCE, On the approximation of shortest common supersequences and longest common subsequences, Large deviations-based upper bounds on the expected relative length of longest common subsequences, Mining Bit-Parallel LCS-length Algorithms, ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS, An artificial neural network based approach for online string matching/filtering of large databases, A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem, Weighted LCS, SYSTEM IDENTIFICATION, APPROXIMATION AND COMPLEXITY, Analogical Proportions in a Lattice of Sets of Alignments Built on the Common Subwords in a Finite Language, FINDING MANY OPTIMAL PATHS WITHOUT GROWING ANY OPTIMAL PATH TREES, Nearly \(k\)-universal words -- investigating a part of Simon's congruence, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Combinator Parsing: A Short Tutorial, Unnamed Item, Unnamed Item, Finding approximate patterns in undirected acyclic graphs, Input-driven pushdown automata for edit distance neighborhood, Unnamed Item, On the decidability of finding a positive ILP-instance in a regular set of ILP-instances, A learning algorithm for the longest common subsequence problem, LCS Approximation via Embedding into Local Non-repetitive Strings, Periodic String Comparison, A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression., Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation, Refinement of the results of recognition of mathematical formulas using the Levenshtein distance, Unnamed Item, Unnamed Item, THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE, Watson–Crick Jumping Finite Automata, APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †, Maximal Common Subsequence Algorithms, The longest common subsequence problem for sequences with nested arc annotations., A branch-and-cut approach to the repetition-free longest common subsequence problem, Constrained tree editing, Performance analysis of some simple heuristics for computing longest common subsequences, A substring-substring LCS data structure, Recovery of missing information in graph sequences by means of reference pattern matching and decision tree learning, Natural discrete-event process forecasting: A decision support system, Using position extrema points to capture shape in on-line handwritten signature verification, Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds, A memetic algorithm with dynamic population management for an integrated production-distribution problem, Generalized LCS, Fast and compact regular expression matching, Approximate regular expression pattern matching with concave gap penalties, Fast approximate matching of words against a dictionary, Breadth-first search strategies for trie-based syntactic pattern recognition, Classes of cost functions for string edit distance, Algorithms for approximate graph matching, Linear-space algorithms that build local alignments from fragments, Super-pattern matching, A simple algorithm for the constrained sequence problems, A subquadratic algorithm for approximate limited expression matching, Two applications of the divide \(\&\) conquer principle in the molecular sciences, Approximating the geometric edit distance, Longest common subsequence in sublinear space, Computing longest (common) Lyndon subsequences, Approximation of graph edit distance based on Hausdorff matching, A hardness result and new algorithm for the longest common palindromic subsequence problem, The undecidability of the unrestricted modified edit distance, Block edit models for approximate string matching, Fast Algorithms for Local Similarity Queries in Two Sequences, Adaptive Computation of the Swap-Insert Correction Distance, Efficient merged longest common subsequence algorithms for similar sequences, Fast Approximate Search in Large Dictionaries, On an alternative sequence comparison statistic of Steele, Fast trie-based method for multiple pairwise sequence alignment, Fast Algorithms for Computing Tree LCS, On the Longest Common Parameterized Subsequence, Unified compression-based acceleration of edit-distance computation, A fully compressed algorithm for computing the edit distance of run-length encoded strings, Sequence Alignment Algorithms for Run-Length-Encoded Strings, Exact algorithms for the repetition-bounded longest common subsequence problem, Levenshtein graphs: resolvability, automorphisms \& determining sets, Absent subsequences in words, Edit-Distance Between Visibly Pushdown Languages, Extending alignments with \(k\)-mismatches and \(\ell\)-gaps, Efficient all path score computations on grid graphs, FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search, A Note on the Relationship between Different Types of Correction Queries, New approaches to the analysis and interpretation of the shape of cyclic signals, A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem, Detecting life signatures with RNA sequence similarity measures, Estimating sequence similarity from read sets for clustering next-generation sequencing data, RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm., An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints, Computing a longest common almost-increasing subsequence of two sequences, Faster STR-EC-LCS Computation, Topology of strings: median string is NP-complete, An algorithm for the sequence alignment with gap penalty problem using multiway divide-and-conquer and matrix transposition, Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition, Using fuzzy logic to match strings in documents, The Cost of Traveling between Languages, Approximation to the mean curve in the LCS problem, APPROXIMATION ALGORITHMS FOR LOCAL ALIGNMENT WITH LENGTH CONSTRAINTS, A bit-string longest-common-subsequence algorithm, Vector representations for efficient comparison and search for similar strings, Function approximation on non-Euclidean spaces, Tandem cyclic alignment, Learning local transductions is hard, An improved algorithm for tree edit distance with applications for RNA secondary structure comparison, Fuzzy automata with \(\varepsilon\)-moves compute fuzzy measures between strings, Unnamed Item, Distance measures for biological sequences: some recent approaches, \(\text{MA}\mid\text{PM}\): memetic algorithms with population management, Tight conditional lower bounds for longest common increasing subsequence, Edit distance-based kernel functions for structural pattern classification, Triangular covers of a digital object, Some limit results for longest common subsequences, Computation of Similarity—Similarity Search as Computation, A diagonal-based algorithm for the longest common increasing subsequence problem, Comparison of strings belonging to the same family, Weighted automata computation of edit distances with consolidations and fragmentations, Optimal matching of deformed patterns with positional influence, Efficient algorithms for approximate string matching with swaps, Maximal common subsequence algorithms, An approach for approximate subgraph matching in fuzzy RDF graph, Hardness results for the center and median string problems under the weighted and unweighted edit distances, Decomposition algorithms for the tree edit distance problem, Some approaches to improve tree-based nearest neighbour search algorithms, How hard is computing the edit distance?, Global and local sequence alignment with a bounded number of gaps, The utilization of fuzzy sets in the recognition of imperfect strings, Fast distance multiplication of unit-Monge matrices, Nearly \(k\)-universal words -- investigating a part of Simon's congruence, A fast and practical bit-vector algorithm for the longest common subsequence problem, Resequencing a set of strings based on a target string, Discovering instances of poetic allusion from anthologies of classical Japanese poems, \(k\)-approximate quasiperiodicity under Hamming and edit distance, Enumeration of maximal common subsequences between two strings, A data structure for substring-substring LCS length queries, A space efficient algorithm for the longest common subsequence in \(k\)-length substrings, Approximate string matching using compressed suffix arrays, Which XML schemas are streaming bounded repairable?, Richard Bellman's contributions to computer science, The principle of optimality in the design of efficient algorithms, A fast algorithm for stereo matching, LCS\(k\): a refined similarity measure, The longest common subsequence problem revisited, Constrained string editing, An \(O(ND)\) difference algorithm and its variations, A coprocessor architecture for fast protein structure prediction, A novel look-ahead optimization strategy for trie-based approximate string matching, Data structures and algorithms for approximate string matching, Calculating distances for dissimilar strings: the shortest path formulation revisited, A memetic algorithm for the travelling salesperson problem with hotel selection, Statistical analysis of distance-based path relinking for the capacitated vehicle routing problem, A lower bound for the edit-distance problem under an arbitrary cost function, Fuzzy trees in decision support systems, Supervised classification and mathematical optimization, VLSI architectures for string matching and pattern matching, Novel evolutionary models and applications to sequence alignment problems, Dynamic programming algorithms for picture comparison, A metric normalization of tree edit distance, Automatic learning of cost functions for graph edit distance, The longest common subsequence problem for arc-annotated sequences, A dynamic edit distance table, An improved algorithm for solving the banded cyclic string-to-string correction problem, A new filtration method and a hybrid strategy for approximate string matching, A survey on tree matching and XML retrieval, A faster algorithm computing string edit distances, Strategy-proof social choice on multiple and multi-dimensional single-peaked domains, Markov network based ontology matching, A sum-over-paths extension of edit distances accounting for all sequence alignments, Fast algorithms for computing the constrained LCS of run-length encoded strings, A theory of subtree matching and tree kernels based on the edit distance concept, A modified tree-to-tree correction problem, The string merging problem, A fast algorithm for the longest-common-subsequence problem, Doubly-constrained LCS and hybrid-constrained LCS problems revisited, The shortest common supersequence problem over binary alphabet is NP- complete, Sequence matching with binary codes, On a cyclic string-to-string correction problem, An O(NP) sequence comparison algorithm, Speeding up the dynamic algorithm for planar RNA folding, A note on some tree similarity measures, An overview on XML similarity: background, current trends and future directions, Context prediction of mobile users based on time-inferred pattern networks: a probabilistic approach, Local similarity between quotiented ordered trees, Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics, Faster algorithms for computing longest common increasing subsequences, Using swaps and deletes to make strings match, Algorithms for computing variants of the longest common subsequence problem, Image categorization: Graph edit distance \(+\) edge direction histogram, Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion, Dynamic edit distance table under a general weighted cost function, On the generalized constrained longest common subsequence problems, Factorization theory: from commutative to noncommutative settings., Hidden Markov model-based ensemble methods for offline handwritten text line recognition, A space efficient algorithm for finding the best nonoverlapping alignment score, An improved algorithm for computing the edit distance of run-length coded strings, Fast linear-space computations of longest common subsequences, Dynamic programming with convexity, concavity and sparsity, An approximate string-matching algorithm, Approximate string-matching with \(q\)-grams and maximal matches, Finding the longest common subsequence for multiple biological sequences by ant colony optimization, On the editing distance between unordered labeled trees, Fitness landscape analysis for the no-wait flow-shop scheduling problem, An algorithm for matching run-length coded strings, Lazy dynamic-programming can be eager, Approximate string matching with suffix automata, Constrained sequence analysis algorithms in computational biology, Learning state machine-based string edit kernels, New efficient algorithms for the LCS and constrained LCS problems, Faster approximate string matching for short patterns, An algorithm with linear expected running time for string editing with substitutions and substring reversals, Efficient algorithms for the block edit problems, Deciding word neighborhood with universal neighborhood automata, Identifying periodic occurrences of a template with applications to protein structure, LR error repair using the A* algorithm, Finite automata based algorithms on subsequences and supersequences of degenerate strings, A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings, A survey on tree edit distance and related problems, A survey of graph edit distance, LCS approximation via embedding into locally non-repetitive strings, Continuous optimization methods for structure alignments, Fast algorithms for computing tree LCS, Combining diverse on-line and off-line systems for handwritten text line recognition, A new efficient algorithm for computing the longest common subsequence, The tree-to-tree editing problem, Dissimilarity between two skeletal trees in a context, A constrained edit distance algorithm between semi-ordered trees, A new constrained edit distance between quotiented ordered trees, Sequence alignment for masquerade detection, The constrained longest common subsequence problem, A robust algorithm for identification of proteins in a database, On the longest common parameterized subsequence, A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling, Computing a longest common subsequence for a set of strings, Line geometries for sequence comparisons, A model and a fast algorithm for multiple errors spelling correction, New algorithms for the LCS problem
