Overlapping markup

In markup languages, overlap occurs when a document has two or more structures that interact in a non-hierarchical manner. A document with overlapping markup cannot be represented as a tree. This is also known as concurrent markup. Overlap happens, for instance, in poetry, where there may be a metrical structure of feet and lines; a linguistic structure of sentences and quotations; and a physical structure of volumes and pages and editorial annotations.^[1][2]

Properties and types

A distinction should be drawn between schemes that allow non-contiguous overlap, and those which allow only contiguous overlap; often, what is meant by 'markup overlap' is strictly the latter. Contiguous overlap can always be represented as a linear document with milestones, without the need for fragmentation and pointers to fragments, but non-contiguous overlap may require document fragmentation. Another distinction in overlapping markup schemes is whether elements can overlap with other elements of the same kind (self-overlap).^[2]

A scheme may have a privileged hierarchy. Some XML-based schemes, for example, represent one hierarchy directly in the XML document tree, and represent other, overlapping, structures by another means; these are said to be non-privileged.

Approaches and implementations

DeRose (2004, Evaluation criteria) identifies several criteria for judging solutions to the overlap problem: readability and maintainability, tool support and compatibility with XML, possible validation schemes, and ease of processing.

Tag soup is, strictly speaking, not overlapping markup—it is malformed HTML, which is a non-overlapping language, and may be ill-defined. HTML5 defines how processors should deal with such mis-nested markup in the HTML syntax and turn it into a single hierarchy.^[3] With XHTML and SGML-based HTML, however, mis-nested markup is a strict error and makes processing by standards-compliant systems impossible.^[4]

SGML, which early versions of HTML were based on, has a feature called CONCUR that allows multiple independent hierarchies to co-exist without privileging any. DTD validation is a challenge when using CONCUR, validation across hierarchies is hard if not impossible, it could not support self-overlap, and it interacted poorly with commonly used SGML features. This feature was poorly supported by tools and saw very little actual use; using CONCUR to represent document overlap was not a recommended use case, according to a commentary by the standard's editor.^[5][6]

Within hierarchical languages

There are several approaches to representing overlap in a non-overlapping language:^[7]

• Multiple documents, which provide different internally consistent hierarchies. The advantage of this approach is that each document is simple and can be processed with existing tools, but requires maintenance of redundant content and it can be difficult to cross-reference between different views.^[8]
• Milestones are empty elements which mark the beginning and end of a component. These can be used to embed a non-privileged structure within a hierarchical language, and can only represent contiguous overlap. Existing tools will also not understand the meaning of the milestone elements and so cannot easily process or validate the non-privileged structure.^[9][10] The markup being near the content is an advantage for maintainability and readability.^[11] CLIX (DeRose 2004) is an example of such an approach.
• Joins are pointers within a privileged hierarchy to other components of the privileged hierarchy, which may be used to reconstruct a non-privileged component akin to following a linked list. A single non-privileged element is segmented into several partial elements within the privileged hierarchy; the partial elements themselves do not represent a single unit in the non-privileged hierarchy, which can be misleading and make processing difficult.^[12][13] While this approach can support some discontiguous structures, it is not able to re-order elements.^[14] A slightly different approach can, however, express re-ordering by expressing the join away from the content, at the cost of directness and maintainability.^[15]
• Stand-off markup is similar to using joins, except that there is no privileged hierarchy: each part of the document is given a label, and the document is constructed by pointing to the content by name in markup which is 'stood off' away from the content, which itself does not contain any content. Validation of stand-off markup is very challenging.^[16] In addition, maintenance is a problem.^[6]

The Text Encoding Initiative, as an XML-based markup scheme, cannot directly represent overlapping markup. All four of the above approaches are suggested.^[1] The Open Scripture Information Standard is another XML-based scheme, designed to mark up the Bible. It uses empty milestone elements to encode non-privileged components.^[17]

New languages

Another approach is to design an entirely new markup language. These forego the tool support in existing languages for a less complicated semantic model and more convenient syntax.

• LMNL is a non-hierarchical markup language first described in 2002 by Jeni Tennison and Wendell Piez, annotating ranges of a document with properties and allowing self-overlap. CLIX, which originally stood for 'Canonical LMNL In XML', provides a method for representing any LMNL document in a milestone-style XML document.^[18] It also has another XML serialisation, xLMNL.^[19]
• MECS was developed by the University of Bergen's Wittgenstein Archive. However, it had several problems: it allowed some non-sensical documents of overlapping elements, it could not support self-overlap, and it did not have the capacity to define a DTD-like grammar.^[20] The theory of General Ordered-Descendant Directed Acyclic Graphs (GODDAGs), while not strictly a markup language itself, is a general data model for non-hierarchical markup. Restricted GODDAGs were designed specifically to match the semantics of MECS; general GODDAGs may be non-contiguous and need a more powerful language.^[21] TexMECS is a successor to MECS, which has a formal grammar and is designed to be capable of representing every GODDAG and nothing that is not a GODDAG.^[22]
• EARMARK is a RDF/OWL representation that encompasses GODDAGs.^[7]
• XCONCUR (previously MuLaX) is a melding-together of XML and SGML's CONCUR, and also contains a validation language, XCONCUR-CL, and a SAX-like API.^[23][24][25]

Conversion and equivalence

Marinelli, Vitali and Zacchiroli provide algorithms to convert between restricted GODDAGs, ECLIX, LMNL, parallel documents in XML, contiguous stand-off markup and TexMECS.^[26]

References

• Sperberg-McQueen, C M; Huitfeldt, Claus (2000). "GODDAG: A Data Structure for Overlapping Hierarchies". Lecture Notes in Computer Science (2023): 139–160. Retrieved 2014-10-14. 
• DeRose, Steven (2004). Markup Overlap: A Review and a Horse. Extreme Markup Languages 2004. Montréal. Retrieved 2014-10-14. 
• Hilbert, Mirco; Schonefeld, Oliver; Witt, Andreas (2005). Making CONCUR work. Extreme Markup Languages 2005. Montréal. Retrieved 2014-10-14. 
• Witt, Andreas; Schonefeld, Oliver; Rehm, Georg; Khoo, Jonathan; Evang, Kilian (2007). On the Lossless Transformation of Single-File, Multi-Layer Annotations into Multi-Rooted Trees. Extreme Markup Languages 2007. Montréal. Retrieved 2014-10-14. 
• Marinelli, Paolo; Vitali, Fabio; Zacchiroli, Stefano (January 2008). "Towards the unification of formats for overlapping markup" (PDF). New Review of Hypermedia and Multimedia 14 (1): 57–94. doi:10.1080/13614560802316145. ISSN 1361-4568. Retrieved 2014-10-14. 
• Schonefeld, Oliver (August 2008). A Simple API for XCONCUR: Processing concurrent markup using an event-centric API. Balisage: The Markup Conference 2008. Montréal. doi:10.4242/BalisageVol1.Schonefeld01. Retrieved 2014-10-14. 
• Di Iorio, Angelo; Peroni, Silvio; Vitali, Fabio (August 2009). Towards markup support for full GODDAGs and beyond: the EARMARK approach. Balisage: The Markup Conference 2009. Montréal. doi:10.4242/BalisageVol3.Peroni01. 
• Text Encoding Initiative Consortium (16 September 2014). "Guidelines for Electronic Text Encoding and Interchange" (5 ed.). Retrieved 2014-10-14.  |chapter= ignored (help)