Equivalences in Euler-based diagram systems through normal forms. Issue Volume 17:Issue A(2014) (September 2014)

• Record Type: Journal Article
• Authors: Fish, Andrew; Taylor, John
• Is Part Of: LMS journal of computation and mathematics. Volume 17:Issue A(2014)
• Page Start: 431
• Page End: 484
• Publication Date: 2014-09
• Subjects: 03B22, -- 03B70 (primary), -- 68R99 (secondary)
• DOI: 10.1112/S1461157014000114
• Languages: English
• ISSNs: 1461-1570

Abstract

Abstract: The form of information presented can influence its utility for the conveying of knowledge by affecting an interpreter's ability to reason with the information. There are distinct types of representational systems (for example, symbolic versus diagrammatic logics), various sub-systems (for example, propositional versus predicate logics), and even within a single representational system there may be different means of expressing the same piece of information content. Thus, to display information, choices must be made between its different representations, depending upon many factors such as: the context, the reasoning tasks to be considered, user preferences or desires (for example, for short symbolic sentences or minimal clutter within diagrammatic systems). The identification of all equivalent representations with the same information content is a sensible precursor to attempts to minimise a metric over this class. We posit that defining notions of semantic redundancy and identifying the syntactic properties that encapsulate redundancy can help in achieving the goal of completely identifying equivalences within a single notational system or across multiple systems, but that care must be taken when extending systems, since refinements of redundancy conditions may be necessary even for conservative system extensions. We demonstrate this theory within two diagrammatic systems, which are Euler-diagram-based notations. Such notations can be used to represent logical information and have applications including visualisation of database queries, social network visualisation, statistical data visualisation, and as the basis of more expressive diagrammatic logics such as constraint languages used in software specification and reasoning. The development of the new associated machinery and concepts required is important in its own right since it increases the growing body of knowledge on diagrammatic logics. In particular, we consider Euler diagrams with shading, and then we conservatively extend the system to include projections, which allow for a much greater degree of flexibility of representation. We give syntactic properties that encapsulate semantic equivalence in both systems, whilst observing that the same semantic concept of redundancy is significantly more difficult to realise as syntactic properties in the extended system with projections.