Visibly Pushdown Languages (VPLs), recognized by Visibly Pushdown Automata
(VPAs), are a nicely behaved family of context-free languages. It has been shown
that VPAs are equivalent to Extended Document Type Definitions (EDTDs), and
thus, they provide means for elegantly solving various problems on XML. One of the
important problems about XML that can be addressed using VPAs is the validation
problem in which we need to decide whether an XML document con- forms to the
schema specification given by an EDTD. In this thesis, we are interested in solving the
approximate version of this problem, which is to decide whether an XML document
can be modified by a tolerable number of edit operations to yield a valid one with
respect to a given EDTD. For this, we define Edit Visibly Pushdown Transducers
(EVPTs) that give us the framework for solving this problem ([23]). We propose two
algorithms; the first algorithm solves the approximate validation for any EDTD in
PTIME. The second algorithm solves the same problem for an interesting subclass of
EDTDs (those rec- ognizable by FSA) in constant space using only a single pass over
the document.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1270 |
| Date | 03 December 2008 |
| Creators | Ye, Ying Ying |
| Contributors | Srinivasan, Venkatesh, Thomo, Alex |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0024 seconds