There exist many approaches to specifying syntax (and to some degree semantics) of visual languages. Mostly, these are based on extensions of string grammar formalisms. A complete and recent overview is out of scope of this paper. However, we like to mention a few approaches: generalizations of attributed grammars (e.g. picture layout grammars [20]), positional grammars (e.g. [21]), and graph grammars (e.g. [22,23,24]). Other approaches closely related to this one use (constraint) logic or relational formalisms (e.g. [25,26,27,28,29,30]) to represent spatial relationships. Experience has shown (reported by Wittenburg in [29]) that some grammar approaches have limitations (e.g. no arbitrary ordering of input, only special relations allowed, connected graphs necessary, bottom-up parsing applicable, no ambiguous grammars, etc.) which are sometimes unacceptable for particular application domains.
Helm and Marriott [26] developed a declarative specification and semantics for VLs. It is based on definite clause logic and implemented with the help of constraint logic programming. Marriott's recent approach is based on these ideas but utilizes constraint multiset grammars [30]. An advantage of our approach is the taxonomic hierarchy of concept definitions and the capabilities to reason about these specifications and their subsumption relationships.
Cohn and Gooday [31] applied the RCC theory to the VL domain and also developed formal semantics for Pictorial Janus. However, their specifications still rely on full predicate logic and cannot gain from the advantages of our DL approach. As far as we know, they currently do not support graphical construction of diagrammatic representations or mechanical verification processes. We also argue that DL notation ---featuring concept and role definitions with inheritance and with a possible extension to concrete domains--- is much more suitable for human and even mechanical inspection. This is an important issue since theories about VLs are still designed by humans.
Citrin et al. [32] also present work on formal semantics of completely visual languages. They developed formal operational semantics for control in the object-oriented language VIPR but their semantics is not based on the graphical representation of the language elements.
Another approach to reasoning with pictorial concepts is based on a different, type-theoretic framework [33,34,35]. An important distinction is that our theory is more expressive with respect to concept definitions. For instance, in [33] the authors suggest to extend their type-theoretic approach by notions such as parameterization for construction of generic concepts and type dependency for describing pictures consisting of parts of other pictures. Our DL theory already handles the intended effects of parameterization and type dependency since its reasoning component automatically maintains a taxonomy of subsuming concept definitions which may share common subparts.
A principal advantage of our approach is the use of necessary and sufficient descriptions, i.e. defined concepts. Logic-based specifications using a Prolog-like style can only define sufficient but not necessary conditions. Our framework is suitable for recognizing (parsing) visual notations as well as constructing examples from specifications. Parsing can even hypothesize unknown information about notation elements. This can be accomplished with the help of ABox reasoning and the underlying model-theoretic semantics. The ABox reasoner verifies a notation example by creating a corresponding model and can automatically proof whether this model is still satisfiable if further assumption about elements are made. Our approach also supports multi-level reasoning and can thus avoid problems with a combinatorial explosion of alternatives in specifications. For instance, imagine the specification of a triangle based on unordered sets of points (representing lines). We can avoid this problem since reasoning can take place about connectedness of points (low-level reasoning) as well as undirected lines (higher-level reasoning).