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 deffne a model of over-lapping or multihierarchical markup that has both a graphbased and a text-and-tags representation. Our model, which we call the range GODDAG, augments the classical GOD-DAG (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 satisffes two conditions previously identiffed 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.