Automata and XML

Frank Neven
Universiteit Hasselt
Friday, 7 December, 2007 (All day)

The advent of XML imposes new and exciting challenges on the field of theoretical computer science. In this talk we present a tutorial style introduction to XML schema languages and their corresponding (unranked) tree and string automata models. We discuss their expressive power, succinctness and the complexity of their decision problems.

The talk covers material from:

  • Wouter Gelade, Frank Neven: Succinctness of Pattern-Based Schema Languages for XML. DBPL 2007: 201-215
  • Wouter Gelade, Wim Martens, Frank Neven: Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. ICDT 2007: 269-283
  • Geert Jan Bex, Frank Neven, Thomas Schwentick, Karl Tuyls: Inference of Concise DTDs from XML Data. VLDB 2006: 115-126
  • Wim Martens, Frank Neven, Thomas Schwentick, Geert Jan Bex: Expressiveness and complexity of XML Schema. ACM Trans. Database Syst. 31(3): 770-813 (2006)
  • Wim Martens, Frank Neven, Thomas Schwentick: Complexity of Decision Problems for Simple Regular Expressions. MFCS 2004: 889-900
  • Wouter Gelade, Frank Neven: succinctness of the complement and intersection of regular expressions.