Efficient Inclusion for a Class of XML Types with Interleaving and Counting

Inclusion between XML types is important but expensive, and is
much more expensive when unordered types are considered. We prove here
that inclusion for XML types with interleaving and counting can be
decided in polynomial time in presence of two important restrictions: 
no element appears twice in the same content model, and Kleene star
is only applied to disjunctions of single elements. 

Our approach is based on the transformation of each such type into a
set of constraints that completely characterizes the
type. We then provide a complete 
deduction system to verify whether the constraints of one type imply
all the constraints of another one.