RWTH Aachen University
An edit script between an (invalid) XML (eXtensible Markup Language) document and a schema is a sequence of edit operations to transform the document into a valid one against the schema. Finding optimum and near optimum edit scripts between an XML document and a schema is essential to correcting invalid XML documents. In this paper, the authors consider finding K optimum edit scripts between an XML document and a regular tree grammar. They first prove that the problem is NP-hard. They next show a pseudopolynomial-time algorithm for solving the problem.