Finding an optimum edit script between an XML document and a DTD
Nobutaka Suzuki · 2005
Finding an optimum edit script between data plays an important role in data retrieval and data transformation. Many methods for finding an optimum edit script between two XML documents have been proposed so far, but few studies on finding an optimum edit script between an XML document and a DTD have been made. In this paper, we first show a polynomial-time algorithm that finds an optimum edit script between an XML document (modeled as an ordered tree) and a DTD. We next prove that, if the cost of an operation on a node in a tree may depend on the other nodes, then the corresponding decision problem becomes strongly NP-complete.