Visibly Pushdown Transducers for Approximate Validation of Streaming XML

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. Especially, it has been shown that VPAs are the apt device for streaming XML. One of the important problems about XML that can be addressed using VPAs is the validation problem in which the authors need to decide whether an XML document conforms to the specification given by an EDTD.