Extending Core Range Algebra to arbitrary structures.
Attributed Range Algebra extends Core Range Algebra to close its one obvious gap: a bare range only tells you where something is in a sequence, not what it is. Markup doesn’t just mark boundaries — it labels them. A <title> tag says “this range is a title,” not merely “something starts here and is this long.”
This paper adds attributes to the range data type — an attributed range, or “arange” — each attribute a name/value pair reachable with the same dot-notation used for start and length. It then works through what that buys you. Attributed ranges are organized into layers: a lexical structure layer captures the tokens of a concrete syntax (start tags, end tags, and so on), and an application structure layer built on top of it imposes a canonical ordering and derives the higher-level structures an application actually cares about — the traditional notion that a <p> element is the parent of the <i> element it contains, for instance. Because everything above the lexical layer only cares about ranges and attributes, not concrete syntax, the paper shows the same application structure recovered from text marked up in XML, LaTeX, and an invented ad hoc notation — the syntax is swappable without touching how the application reasons about structure. One practical consequence: because markup is just a range, an entire class of elements can be suppressed from a document non-destructively simply by removing the corresponding ranges.