A Probabilistic Analysis of a String Editing Problem and its Variations

DOI10.1017/S0963548300001541zbMath0831.60016MaRDI QIDQ4852430

Wojciech Szpankowski, Guy Louchard

Publication date: 25 January 1996

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

zbMATH Keywords

generating functionsrandom walksdiffusion limiting processesstring editing problem in a probabilistic framework

Mathematics Subject Classification ID

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

Cites Work

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

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