  XrML is becoming a popular language in industry for writing software
licenses. The semantics for XrML is implicitly given by an algorithm that
determines if a permission follows from a set of licenses. We focus on a
fragment of the language and use it to highlight some problematic aspects of
the algorithm. We then correct the problems, introduce formal semantics, and
show that our semantics captures the (corrected) algorithm. Next, we consider
the complexity of determining if a permission is implied by a set of XrML
licenses. We prove that the general problem is undecidable, but it is
polynomial-time computable for an expressive fragment of the language. We
extend XrML to capture a wider range of licenses by adding negation to the
language. Finally, we discuss the key differences between XrML and MPEG-21, an
international standard based on XrML.
