๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The Computational Hardness of Estimating Edit Distance

โœ Scribed by Andoni, Alexandr; Krauthgamer, Robert


Book ID
118181033
Publisher
Society for Industrial and Applied Mathematics
Year
2010
Tongue
English
Weight
438 KB
Volume
39
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.


๐Ÿ“œ SIMILAR VOLUMES


Fast computation of distance estimators
โœ Isaac Elias; Jens Lagergren ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› BioMed Central ๐ŸŒ English โš– 710 KB
The undecidability of the unrestricted m
โœ Vitus J. Leung ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 704 KB

We define the unrestricted modified edit distance based on the modified edit distance defined by Galil and Giancarlo (1989) where the cost of substring deletions and insertions are contextsensitive and the cost of character substitutions are context-free. The modified edit distance is the minimum co