Bounds and estimates on the average edit distance

DOI10.1007/978-3-030-32686-9_7MaRDI QIDQ6536246zbMATH OpenFDO

Authors Michele Schimd, Gianfranco Bilardi

Publication date 19 April 2024

Full work available at URL https://doi.org/10.1007/978-3-030-32686-9_7

zbMATH Keywords

average analysisedit distancestatistical estimatesupper and lower bounds

Mathematics Subject Classification ID

Parametric tolerance and confidence regions (62F25) Algorithms on strings (68W32)

Recommendations

• A Probabilistic Analysis of a String Editing Problem and its Variations
• The computational hardness of estimating edit distance
• String editing under a combination of constraints
• scientific article; zbMATH DE number 3845091
• A lower bound for the edit-distance problem under an arbitrary cost function

Cites work

• A faster algorithm computing string edit distances
• Bounding the expected length of longest common subsequences and forests
• Computing the expected edit distance from a string to a probabilistic finite-state automaton
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Hardness of approximate nearest neighbor search
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Improved bounds on the average length of longest common subsequences
• Longest common subsequences of two random sequences

Cited in

(1)

• Volume formula and growth rates of the balls of strings under the edit distances

This page was built for publication: Bounds and estimates on the average edit distance

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