Edit distance with block deletions (Q1736478)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Edit distance with block deletions
scientific article

    Statements

    Edit distance with block deletions (English)
    0 references
    0 references
    0 references
    0 references
    26 March 2019
    0 references
    Summary: Several variants of the edit distance problem with block deletions are considered. Polynomial time optimal algorithms are presented for the edit distance with block deletions allowing character insertions and character moves, but without block moves. We show that the edit distance with block moves and block deletions is NP-complete (Nondeterministic Polynomial time problems in which any given solution to such problem can be verified in polynomial time, and any NP problem can be converted into it in polynomial time), and that it can be reduced to the problem of non-recursive block moves and block deletions within a constant factor.
    0 references
    approximation algorithms
    0 references
    text processing
    0 references
    NP-completeness
    0 references
    edit distance
    0 references
    dynamic programming
    0 references
    block operations
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references