| Presentation | 2006-10-18 An Edit Operation-Based Approach to the Inclusion Problem for DTDs Nobutaka SUZUKI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | XML documents on a database should be revalidated whenever a DTD is updated, since the documents may no longer be valid against the DTD. Solving the inclusion problem for DTDs is essential to avoiding such an expensive revalidation, but the problem is shown to be PSPACE-complete. In this paper, we propose a subproblem of the inclusion problem in terms of edit operations to regular expressions, and show a polynomial-time algorithm for solving the subproblem. Then we consider the recognizability of the algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | XML / DTD / inclusion problem / regular expression |
| Paper # | DE2006-127,DC2006-34 |
| Date of Issue |
| Conference Information | |
| Committee | DE |
|---|---|
| Conference Date | 2006/10/11(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 | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Edit Operation-Based Approach to the Inclusion Problem for DTDs |
| Sub Title (in English) | |
| Keyword(1) | XML |
| Keyword(2) | DTD |
| Keyword(3) | inclusion problem |
| Keyword(4) | regular expression |
| 1st Author's Name | Nobutaka SUZUKI |
| 1st Author's Affiliation | Graduate School of Library, Information and Media Studies University of Tsukuba() |
| Date | 2006-10-18 |
| Paper # | DE2006-127,DC2006-34 |
| Volume (vol) | vol.106 |
| Number (no) | 291 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |