A Formal Foundation for XrML 2025

The document presents a formal foundation for the eXtensible rights Markup Language (XrML), which is used for writing software licenses. It critiques the existing algorithm for determining permissions based on XrML licenses, identifies its shortcomings, and proposes formal semantics to address these issues. The authors demonstrate that while the general problem of determining if a permission follows from a set of licenses is undecidable, it can be computed in polynomial time for a specific fragment of the language. They also extend XrML to include negation, enhancing its expressive power. Additionally, the paper compares XrML with MPEG-21, an international standard based on XrML, and discusses implications for digital rights management.