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) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
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 |