[Date Prev][Date Next][Date Index]

TALK ANNOUNCEMENT: XML Schemas Admitting 1-Pass Preorder Typing

Date: Jan 3, 2005; 14:30 s.t.

Location Seminarraum 184/2

Title: XML Schemas Admitting 1-Pass Preorder Typing

Wim Martens


  It is shown that the class of regular tree languages admitting
  one-pass preorder typing is exactly the class defined by restrained
  competition tree grammars introduced by Murata et
  al., 2001. In a streaming context, the former is
  the largest class of XSDs where every element in a document can be
  typed when its opening tag is met. The main technical machinery
  consists of semantical characterizations of restrained competition
  grammars and their subclasses. In particular, they can be
  characterized in terms of the context of nodes, closure properties,
  allowed patterns and guarded DTDs. It is further shown that deciding
  whether a schema is restrained competition is tractable.  Deciding
  whether a schema is equivalent to a restrained competition tree
  grammar, or one of its subclasses, is much more difficult: it is
  complete for EXPTIME.  We show that our semantical
  characterizations allow for easy optimization and minimization
  algorithms. Finally, we relate the notion of one-pass preorder
  typing to the existing XML Schema standard.