reconciling two models of multihierarchical markup
For documents with complex or atypical annotations, multihierarchical structures play the role of the document tree in traditional XML documents. We define a model of overlapping or multihierarchical markup that has both a graph-based and a text-and-tags representation. Our model, which we call the range GODDAG, augments the classical GODDAG (generalized ordered-descendant DAG) structure with order relations over the nodes, and additional constraints that ensure documents have a convenient serialization in terms of tagged text. We provide two alternative constructions for this new model, and prove that documents in the model have (1) a unique representation as a graph, and (2) a straightforward textual representation that satisfies two conditions previously identified as important for serialization. Furthermore, we show how the range GODDAG provides a convenient way to characterize the update operations that may be performed on a document while maintaining serializability.
text markup multihierarchical documents overlapping markup