Paper announcement: Validation and boolean operations for attribute-element constraints

Dear folks,

We are pleased to announce the availability of our new paper

  Validation and boolean operations for attribute-element constraints

by Haruo Hosoya and Makoto Murata.  This paper is concerned with core
algorithms that are needed in implementing a statically typed language
for XML processing.  The PS file of the paper can be retrieved from:


Comments and questions are welcome.


Haruo Hosoya
Makoto Murata


Algorithms for validation and boolean operations play a crucial role
in developing XML processing systems involving schemas.  Although
much effort has previously been made for treating {\em elements}, very
few studies have paid attention to {\em attributes}.  This paper
presents a validation and boolean algorithms for Clark's
attribute-element constraints.  Although his mechanism has a prominent
expressiveness and generality among other proposals, treating this is
algorithmically challenging since naive approaches easily blow up even
for typical inputs.  To overcome this difficulty, we have developed
(1) a two-phase validation algorithm that uses what we call {\em
  attribute-element automata} and (2) intersection and difference
algorithms that proceed by a ``divide-and-conquer'' strategy.