×

Equivalences in Euler-based diagram systems through normal forms. (English) Zbl 1348.03029

Summary: 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.

MSC:

03B70 Logic in computer science
03B22 Abstract deductive systems
68T27 Logic in artificial intelligence

Software:

Hyperproof
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Delaney, Proceedings of 6th International Conference on the Theory and Application of Diagrams, Portland, OR pp 69– (2010)
[2] Delaney, Proceedings of the VLL 2007 Workshop on Visual Languages and Logic, CEUR-WS.org/Vol-274 (CEUR, Idaho, 2007) pp 27–
[3] DeChiara, Proceedings of Information Visualisation pp 120– (2003)
[4] Dau, 16th International Conference on Conceptual Structures pp 104– (2008)
[5] DOI: 10.1016/j.jvlc.2007.12.003 · Zbl 05696176 · doi:10.1016/j.jvlc.2007.12.003
[6] DOI: 10.1109/TVCG.2011.56 · doi:10.1109/TVCG.2011.56
[7] Dau, Proc. ICCS 2008 pp 104– (2008)
[8] DOI: 10.1080/14786448008626877 · doi:10.1080/14786448008626877
[9] Cordasco, Proc. VL/HCC 2009 pp 185– (2009)
[10] DOI: 10.1016/j.jvlc.2013.07.002 · doi:10.1016/j.jvlc.2013.07.002
[11] Thièvre, Euler Diagrams 2004 pp 189– (2005)
[12] DOI: 10.1109/TVCG.2009.122 · doi:10.1109/TVCG.2009.122
[13] DOI: 10.1016/j.jvlc.2012.10.007 · doi:10.1016/j.jvlc.2012.10.007
[14] DOI: 10.1007/s10270-003-0044-8 · Zbl 02243156 · doi:10.1007/s10270-003-0044-8
[15] DOI: 10.1023/A:1009712514511 · doi:10.1023/A:1009712514511
[16] DOI: 10.1093/logcom/14.6.857 · Zbl 1067.03015 · doi:10.1093/logcom/14.6.857
[17] Bertault, Proceedings of the 8th International Symposium on Graph Drawing pp 164– (2000)
[18] DOI: 10.1007/s10817-007-9069-y · Zbl 1132.68683 · doi:10.1007/s10817-007-9069-y
[19] Barwise, Logical reasoning with diagrams (1996) · Zbl 0870.03002
[20] Stapleton, Visual Languages and Computing 2007 pp 187– (2007)
[21] Barwise, Logical reasoning with diagrams pp 3– (1996) · Zbl 0870.03002
[22] DOI: 10.1016/j.tcs.2009.09.005 · Zbl 1189.68134 · doi:10.1016/j.tcs.2009.09.005
[23] Barwise, Hyperproof (1994)
[24] Stapleton, 19th International Conference on Distributed Multimedia Systems, Visual Languages and Computing pp 182– (2013)
[25] DOI: 10.1145/182.358434 · Zbl 0519.68079 · doi:10.1145/182.358434
[26] DOI: 10.1016/j.jvlc.2008.04.003 · Zbl 05696174 · doi:10.1016/j.jvlc.2008.04.003
[27] Knowledge representation: logical, philosophical, and computational foundations (2000)
[28] DOI: 10.1111/j.1467-8659.2009.01452.x · Zbl 05650562 · doi:10.1111/j.1467-8659.2009.01452.x
[29] Shin, The logical status of diagrams (1994) · Zbl 0829.03002
[30] DOI: 10.1007/978-3-540-25931-2_3 · doi:10.1007/978-3-540-25931-2_3
[31] Ruskey, Electron. J. Combin. (1997)
[32] DOI: 10.1109/TVCG.2010.210 · doi:10.1109/TVCG.2010.210
[33] DOI: 10.2307/2963899 · Zbl 0098.24501 · doi:10.2307/2963899
[34] DOI: 10.1016/j.jda.2012.04.013 · Zbl 1255.68193 · doi:10.1016/j.jda.2012.04.013
[35] DOI: 10.1016/j.jvlc.2008.01.004 · Zbl 05696183 · doi:10.1016/j.jvlc.2008.01.004
[36] Papadimitriou, 14th Conference on Artificial Intelligence pp 901– (1995)
[37] DOI: 10.1111/j.1551-6708.1987.tb00863.x · doi:10.1111/j.1551-6708.1987.tb00863.x
[38] DOI: 10.1186/1471-2105-9-67 · doi:10.1186/1471-2105-9-67
[39] DOI: 10.1093/bioinformatics/bti169 · doi:10.1093/bioinformatics/bti169
[40] Kent, Proceedings of OOPSLA97 pp 327– (1997)
[41] Karnaugh, Trans. Amer. Inst. Electr. Eng. 72 pp 593– (1953)
[42] DOI: 10.1002/jgt.3190110306 · Zbl 0654.05055 · doi:10.1002/jgt.3190110306
[43] John, Proceedings of 4th International Conference on the Theory and Application of Diagrams pp 267– (2006)
[44] DOI: 10.1007/s10270-003-0036-8 · Zbl 02243161 · doi:10.1007/s10270-003-0036-8
[45] DOI: 10.1016/j.jvlc.2011.01.002 · doi:10.1016/j.jvlc.2011.01.002
[46] Fish, Diagrammatic representation and inference, 5th International Conference, Diagrams 2008, Herrsching, Germany, September 19–21, 2008 pp 206– (2008)
[47] DOI: 10.1016/j.jvlc.2005.03.001 · Zbl 05696101 · doi:10.1016/j.jvlc.2005.03.001
[48] Fish, Proceedings of Euler Diagrams 2004, Brighton, UK pp 77– (2005)
[49] Euler, Lett. Soc. Typograph. Berne 2 pp 102– (1775)
[50] DOI: 10.1080/02693799508902030 · doi:10.1080/02693799508902030
[51] DOI: 10.1006/jvlc.1995.1010 · doi:10.1006/jvlc.1995.1010
[52] Delaney, Proceedings of 5th International Conference on the Theory and Application of Diagrams, Herrsching, Germany pp 172– (2008)
[53] John, Euler diagrams 2004 pp 103– (2005)
[54] John, Proceedings of 3rd International Conference on the Theory and Application of Diagrams Lecture Notes in Artificial Intelligence 2980 pp 147– (2004)
[55] Sowa, Conceptual structures: information processing in mind and machine (1984) · Zbl 0536.68077
[56] Jamnik, Proceedings of the 15th International Joint Conference on Artificial Intelligence 1 pp 528– (1997)
[57] Jamnik, Mathematical reasoning with diagrams (2001)
[58] DOI: 10.1007/978-3-642-25073-6_17 · Zbl 05980610 · doi:10.1007/978-3-642-25073-6_17
[59] DOI: 10.1112/S1461157000000942 · Zbl 1074.03006 · doi:10.1112/S1461157000000942
[60] Howse, Proceedings of 2nd International Conference on the Theory and Application of Diagrams, Georgia, USA pp 76– (2002)
[61] DOI: 10.1006/jvlc.2000.0210 · Zbl 05695996 · doi:10.1006/jvlc.2000.0210
[62] Howse, Proceedings of 2nd International Conference on the Theory and Application of Diagrams, Georgia, USA pp 146– (2002)
[63] Howse, Proceedings of 2nd International Conference on Formal Ontology in Information Systems, Maine, USA pp 174– (2001)
[64] Hegarty, Proceedings of 3rd International Conference on the Theory and Application of Diagrams pp 1– (2004)
[65] DOI: 10.1145/136586.136589 · doi:10.1145/136586.136589
[66] Harel, Diagrammatic reasoning pp 235– (1998)
[67] DOI: 10.1080/01445349808837293 · Zbl 1052.03516 · doi:10.1080/01445349808837293
[68] Hammer, J. Philos. Logic 25 pp 463– (1996)
[69] Hammer, Logic and visual information (1995) · Zbl 0930.03002
[70] DOI: 10.1023/A:1004924423245 · Zbl 0899.05015 · doi:10.1023/A:1004924423245
[71] Gurr, Proceedings of 22nd International Conference on Software Engineering pp 509– (2000)
[72] DOI: 10.1006/jvlc.1999.0130 · doi:10.1006/jvlc.1999.0130
[73] DOI: 10.2307/2686332 · Zbl 0995.03510 · doi:10.2307/2686332
[74] DOI: 10.1006/jvlc.2000.0199 · Zbl 05696018 · doi:10.1006/jvlc.2000.0199
[75] Gil, Proc. IEEE Symposium on Visual Languages pp 119– (2000)
[76] DOI: 10.1007/s10270-004-0074-x · Zbl 02243128 · doi:10.1007/s10270-004-0074-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.