Presentation 2004/5/31
A Method for Finding an Optimum Transformation for Correcting Invalid XML Documents
Nobutaka SUZUKl,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) We consider finding an optimum transformation to correct an invalid XML document w.r.t. a DTD. To transform an XML document, we treat the document as an ordered tree and apply to the tree three kinds of operations (i)add(adding a new node), (ii)del(deleting an existing node), and (iii)upd(updating the label of a node), where each operation has a cost . We first show a polynomial-time algorithm for finding the optimum cost to transform an invalid XML document into a valid one. We next prove that if the cost of an operation on a node n depends on nodes other than n, then the problem of deciding if there exists a sequence s of operations to transform a given invalid XML document into a valid one at cost no greater than K is strongly NP-complete.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) XML / DTD / document transformation / strong NP-completeness
Paper # DE2004-3
Date of Issue

Conference Information
Committee DE
Conference Date 2004/5/31(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Vice Chair

Paper Information
Registration To Data Engineering (DE)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) A Method for Finding an Optimum Transformation for Correcting Invalid XML Documents
Sub Title (in English)
Keyword(1) XML
Keyword(2) DTD
Keyword(3) document transformation
Keyword(4) strong NP-completeness
1st Author's Name Nobutaka SUZUKl
1st Author's Affiliation Graduate School of Library, Information and Media Studies University of Tsukuba()
Date 2004/5/31
Paper # DE2004-3
Volume (vol) vol.104
Number (no) 102
Page pp.pp.-
#Pages 6
Date of Issue