A Probabilistic Analysis of a String Editing Problem and its Variations

DOI10.1017/S0963548300001541MaRDI QIDQ4852430zbMATH OpenFDO

Authors Wojciech Szpankowski, Guy Louchard

Publication date 25 January 1996

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548300001541

zbMATH Keywords

diffusion limiting processesgenerating functionsrandom walksstring editing problem in a probabilistic framework

Mathematics Subject Classification ID

Graph theory (05C99) Combinatorial probability (60C05)

Recommendations

• scientific article; zbMATH DE number 3883626
• Computing the expected edit distance from a string to a probabilistic finite-state automaton
• Efficiently approximating edit distance between pseudorandom strings
• NP-completeness of special string editing problems
• An algorithm with linear expected running time for string editing with substitutions and substring reversals
• The most probable string: an algorithmic study
• scientific article; zbMATH DE number 2090203
• scientific article; zbMATH DE number 8125

Cites work

• A phase transition for the score in matching random sequences allowing deletions
• A probabilistic analysis of a pattern matching problem
• An \(O(ND)\) difference algorithm and its variations
• An extreme value theory for sequence matching
• An Improved Algorithm For Approximate String Matching
• Asymptotic Limits for a Two-Dimensional Recursion
• Chain Lengths in Certain Random Directed Graphs
• Counts of long aligned word matches among random letter sequences
• Critical phenomena in sequence matching
• Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis
• Efficient Parallel Algorithms for String Editing and Related Problems
• scientific article; zbMATH DE number 3755865 (Why is no real title available?)
• scientific article; zbMATH DE number 194302 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• Limit distributions of maximal segmental score among Markov-dependent partial sums
• Longest common subsequences of two random sequences
• On the number of alignments of k sequences
• Poisson approximations for r-scan processes
• Random walks, Gaussian processes and list structures
• Sequence Alignments with Matched Sections
• The Erdős-Rényi law in distribution, for coin tossing and sequence matching
• The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
• The longest common subsequence problem revisited
• The theory and computation of evolutionary distances: Pattern recognition
• Weak convergence inapplied probability

Cited in

(3)

• scientific article; zbMATH DE number 3883626 (Why is no real title available?)
• A sum-over-paths extension of edit distances accounting for all sequence alignments
• Bounds and estimates on the average edit distance

This page was built for publication: A Probabilistic Analysis of a String Editing Problem and its Variations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4852430)