Toward a formal model of markup.
Core Range Algebra is a small formal algebra for modeling structure in sequences of data — text in particular — without requiring the data to already be broken into a well-formed tree.
Most formal models of XML treat it as semistructured data: an edge-labeled graph, or a tree of nodes. That works well when structure is what matters most, but it runs into trouble the moment you want to query or manipulate text that spans node boundaries — the result of such an operation isn’t necessarily a well-formed XML document, and most tree-based models aren’t closed over that kind of operation.
This paper starts from a different pair of primitives. A sequence is just an ordered list of items; a range is a {start, length} marker into a sequence. The paper builds an algebra of operations over both — union, intersection, concatenation over sequences, and a family of predicates over ranges (StartsWithin, EndsWithin, Within, and so on) for describing how two ranges relate to each other. Because a range is only a position and a length, rather than a node in a tree, ranges are free to overlap — something ordinary markup languages don’t allow. The paper also shows how a sequence of ranges can be used to derive parent/child/ancestor/descendant relationships, deriving hierarchical structure from a flat set of ranges rather than assuming the hierarchy up front.
Written in 2002 while I was CTO of Red Bridge Interactive, this became the basis for a follow-on paper, Attributed Range Algebra, and was presented, alongside that later work, at Extreme Markup 2002 in Montreal.