Visiting Scientist

Uso di logica lineare per la specifica di linguaggi e ambienti visivi. Like written textual languages and their spoken equivalents, many other types of symbolic notations, for example musical scores, can be regarded as languages. By “languages” we mean that they constitute communication systems based on symbol combinations and that they are, at least in principle, formalizable. Where such systems are visual or graphical in nature, it is thus justified to speak of “visual languages”. However, this term is ambiguous: we often speak of the “visual language” of an artist to describe the artist’s particular way of expressing himself or herself. This almost never means that we could define a formal system of expression that the artist uses and through which we could mechanically derive an “interpretation” of a work. In contrast, the syntax and semantics of more technical visual languages, such as organizational charts, dance notation, electrical circuit diagrams and mathematical notations, can often be formalized rigorously. A whole spectrum of semi-formal visual languages exists between these two extremes, ranging from draft sketches in architectural design over maps to sign languages, such as ASL or Auslan. In general, visual languages do not only differ in the degree to which they are strict and can be formalized, but also in the degree to which they use distinct symbols as their fundamental means of expression. For example, a valve in a mechanical diagram is clearly a distinct symbol, whereas it is not so clear whether shading in a map can or should always be understood in the same way. For the sake of clarity, we will use the term “diagrammatic languages” for visual languages that are based on individual symbols and form expressions through spatial arrangement of these symbols. As is evident from the examples above, such diagrammatic languages are central in almost all technical domains, and they are also relevant to many aspects of everyday life. The research field of “diagrammatic reasoning” investigates such languages from the perspective of computer science and cognitive science. The central questions for this field are how we understand such languages and how we employ them as tools in reasoning processes. To investigate these questions in a rigorous way we need formal frameworks that allow us to define diagrammatic languages and to reason about them. From the perspective of computer science, we are particularly interested in how interpretation and reasoning can be performed automatically on the basis of formal specifications of diagrammatic languages. It seems obvious that the treatment of diagrammatic languages should distinguish between syntax and semantics, just as we do for textual languages, and that a general framework needs to bridge between these two aspects. The treatment of diagram syntax has been investigated for close to three decades and is now reasonably well-understood. The vast majority of methods that are employed are essentially generalizations of approaches from computational linguistics for textual languages, mostly grammar frameworks. However, as diagrammatic notations are inherently two- or three-dimensional rather than linear (as textual languages are), these grammar frameworks have to be extended. This has given rise to the field of multi-dimensional grammars. The various forms of multi-dimensional grammars, such as relational grammars, multiset grammars and constraint multiset grammars, are now relatively mature formalisms that are widely used to specify diagram syntax and to build computational tools for diagrammatic languages. The majority of computational methods for the automatic interpretation of diagrams take a syntax-based two-step approach consisting of parsing and interpretation proper, and multi-dimensional grammar frameworks are well-suited to cover the first phase. However, when it comes to the interpretation proper, i.e. the treatment of semantics, they provide little support. Thus, this phase is most often covered by ad-hoc approaches defined on a case-by-case basis for individual diagram languages. Grammar-based methods also have some other shortcomings: Firstly, it is important to acknowledge that diagrams are rarely used in isolation, but rather in combination with textual language. Thus, the interpretation of diagrammatic languages needs to take into account non-diagrammatic contextual information, for example for disambiguation. In a grammatical framework the integration of such contextual information is difficult. Secondly, while multi-dimensional grammars are relatively mature computational tools, their theory is not well developed, meaning that it is difficult, for instance, to prove formal properties, such as the equivalence of grammars. In the light of these shortcomings, logic approaches present themselves as a valuable alternative to grammatical frameworks. Logic approaches, by their very nature, are semantic. A logic calculus for reasoning with and about diagrammatic languages is thus a more adequate approach to treating semantics. Interestingly, the increased power of a logic specification over a grammatical one does not come at a price, as a well-designed logic approach can fully subsume the grammatical approach. The remainder of the chapter will trace out the progress that the last two decades of research have made in this direction. In the next section we will briefly outline the grammatical approach to visual language specification and highlight its shortcomings as a basis for this research plan. We will then revisit the question why do we want reasoning with diagram languages? to motivate an alternative approach. This section will also outline what forms of reasoning will be required. Following this, we will outline the history of logic approaches to diagrammatic languages and detail the comparative advantages and disadvantages of the different types of logic formalization. Based on this, the core of this chapter will develop a new approach, based on linear logic, which avoids most of the shortcomings and completely subsumes the grammatical approach. We will show this subsumption formally. We will then briefly outline existent software systems based on this approach. The concluding section reflects on what has been achieved so far and gives recommendations for future research direction.