Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-20T01:45:07.355Z Has data issue: false hasContentIssue false
  • English
  • Français

Equivalences in Euler-based diagram systems through normal forms

Part of: Discrete mathematics in relation to computer science General logic

Published online by Cambridge University Press:  01 September 2014

Andrew Fish  and
John Taylor
Andrew Fish
Affiliation:
School of Computing Engineering and Mathematics, University of Brighton, Brighton, United Kingdom email [email protected]
John Taylor
Affiliation:
School of Computing Engineering and Mathematics, University of Brighton, Brighton, United Kingdom email [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 classification

Secondary: 03B22: Abstract deductive systems 03B70: Logic in computer science 68R99: None of the above, but in this section
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Issue 1 , 2014 , pp. 431 - 484
Copyright
© The Author(s) 2014 

References

Knowledge representation: logical, philosophical, and computational foundations (Brooks Cole Publishing Co., Pacific Grove, CA, 2000).Google Scholar
Allen, J. F., ‘Maintaining knowledge about temporal intervals’, Commun. ACM 26 (1983) no. 11, 832–843.CrossRefGoogle Scholar
Barwise, J. and Etchemendy, J., Hyperproof (CSLI Press, Stanford, CA, 1994).Google Scholar
Barwise, J. and Etchemendy, J., ‘Visual information and valid reasoning’, Logical reasoning with diagrams (eds Allwein, G. and Barwise, J.; Oxford University Press, Oxford, 1996) 3–25.Google Scholar
Barwise, J. and Hammer, E., ‘Diagrams and the concept of logical system’, Logical reasoning with diagrams (eds Allwein, G. and Barwise, J.; Oxford University Press, Oxford, 1996).Google Scholar
Bertault, F. and Eades, P., ‘Drawing hypergraphs in the subset standard’, Proceedings of the 8th International Symposium on Graph Drawing , Lecture Notes in Computer Science 1984 (Springer, Berlin, 2000) 164–169.Google Scholar
Bottoni, P., Fish, A. and Parisi-Presicce, F., ‘Spider graphs: a graph transformation system for spider diagrams’, Softw. Syst. Model. 10.1007/s10270-013-0381-1.Google Scholar
Bottoni, P. and Fish, A., ‘Extending spider diagrams for policy definition’, J. Vis. Lang. Comput. 24 (2013) no. 3, 169–191.CrossRefGoogle Scholar
Chapman, P., Stapleton, G. and Delaney, A., ‘On the expressiveness of second-order spider diagrams’, J. Vis. Lang. Comput. 24 (2013) 327–349.CrossRefGoogle Scholar
Chow, S. C., ‘Generating and drawing area-proportional Euler and Venn diagrams’, PhD Thesis, University of Victoria, 2007.Google Scholar
Cohn, A. G., Bennett, B., Gooday, J. and Gotts, N. M., ‘Qualitative spatial representation and reasoning with the region connection calculus’, Geoinformatica 1 (1997) no. 3, 275–316.CrossRefGoogle Scholar
Collins, C., Penn, G. and Carpendale, S., ‘Bubble sets: revealing set relations with isocontours over existing visualisations’, IEEE Trans. Vis. Comput. Graphics 15 (2009) no. 6, 1009–1016.CrossRefGoogle Scholar
Cordasco, G., De Chiara, R. and Fish, A., ‘Interactive visual classification with Euler diagrams’, Proc. VL/HCC 2009 (IEEE Computer Society Press, Los Alamitos, CA, 2009) 185–192.Google Scholar
Dau, F. and Fish, A., ‘Conceptual spider diagrams’, Proc. ICCS 2008 , Lecture Notes in Computer Science 5113 (Springer, New York, 2008) 104–118.Google Scholar
Dau, F. and Eklund, P., ‘A diagrammatic reasoning system for the description logic ALC’, J. Vis. Lang. Comput. 19 (2008) no. 5, 539–573.CrossRefGoogle Scholar
Dau, F. and Fish, A., ‘Conceptual spider diagrams’, 16th International Conference on Conceptual Structures , Lecture Notes in Computer Science 5113 (Springer, New York, 2008) 104–118.Google Scholar
DeChiara, R., Erra, U. and Scarano, V., ‘VennFS: A Venn diagram file manager’, Proceedings of Information Visualisation (IEEE Computer Society Press, Los Alamitos, CA, 2003) 120–126.Google Scholar
Delaney, A. and Stapleton, G., ‘Spider diagrams of order’, Proceedings of the VLL 2007 Workshop on Visual Languages and Logic, CEUR-WS.org/Vol-274 (CEUR, Idaho, 2007) 27–39.Google Scholar
Delaney, A., Stapleton, G., Taylor, J. and Thompson, S., ‘Fragments of spider diagrams of order and their relative expressiveness’, Proceedings of 6th International Conference on the Theory and Application of Diagrams, Portland, OR , Lecture Notes in Artificial Intelligence 6170 (Springer, Berlin, 2010) 69–83.Google Scholar
Delaney, A., Taylor, J. and Thompson, S., ‘Spider diagrams of order and a hierarchy of star-free regular languages’, Proceedings of 5th International Conference on the Theory and Application of Diagrams, Herrsching, Germany , Lecture Notes in Artificial Intelligence 5223 (Springer, Berlin, 2008) 172–187.Google Scholar
Eades, P., Lai, W., Misue, K. and Sugiyama, K., ‘Layout adjustment and the mental map’, Vis. Lang. Comput. 6 (1995) 183–210.Google Scholar
Eigenhofer, M. and Franzosa, R., ‘On the equivalence of topological relations’, Int. J. Geogr. Inf. Syst. 9 (1995) no. 2, 133–152.CrossRefGoogle Scholar
Euler, L., ‘Lettres a une princesse dallemagne sur divers sujets de physique et de philosophie’, Lett. Soc. Typograph. Berne 2 (1775) 102–108.Google Scholar
Fish, A. and Flower, J., ‘Abstractions of Euler diagrams’, Proceedings of Euler Diagrams 2004, Brighton, UK , Electronic Notes in Theoretical Computer Science 134 (Elsevier, Amsterdam, 2005) 77–101.Google Scholar
Fish, A., Flower, J. and Howse, J., ‘The semantics of augmented constraint diagrams’, J. Vis. Lang. Comput. 16 (2005) 541–573.CrossRefGoogle Scholar
Fish, A., John, C. and Taylor, J., ‘A normal form for Euler diagrams with shading’, Diagrammatic representation and inference, 5th International Conference, Diagrams 2008, Herrsching, Germany, September 19–21, 2008 , Lecture Notes in Computer Science 5223 (Springer, Berlin, 2008) 206–221.CrossRefGoogle Scholar
Fish, A., Khazaei, B. and Roast, C., ‘User comprehension of Euler diagrams’, J. Vis. Lang. Comput. 22 (2011) no. 5, 340–354.CrossRefGoogle Scholar
Flower, J., Howse, J. and Taylor, J., ‘Nesting in Euler diagrams: syntax, semantics and construction’, Softw. Syst. Modell. 3 (2004) 55–67.CrossRefGoogle Scholar
Flower, J., Fish, A. and Howse, J., ‘Euler diagram generation’, Vis. Lang. Comput. 19 (2008) no. 6, 675–694.CrossRefGoogle Scholar
Gil, J., Howse, J., Kent, S. and Taylor, J., ‘Projections in Venn–Euler diagrams’, Proc. IEEE Symposium on Visual Languages (IEEE Computer Society Press, Los Alamitos, CA, 2000) 119–126.Google Scholar
Gil, J., Howse, J. and Tulchinsky, E., ‘Positive semantics of projections’, J. Vis. Lang. Comput. 13 (2001) no. 2, 197–227.CrossRefGoogle Scholar
Grunbaum, B., ‘The construction of Venn diagrams’, College Math. J. 15 (1984) no. 3, 238–247.CrossRefGoogle Scholar
Gurr, C., ‘Effective diagrammatic communication: syntactic, semantic and pragmatic issues’, J. Vis. Lang. Comput. 10 (1999) no. 4, 317–342.CrossRefGoogle Scholar
Gurr, C. and Tourlas, K., ‘Towards the principled design of software engineering diagrams’, Proceedings of 22nd International Conference on Software Engineering (ACM Press, New York, 2000) 509–518.CrossRefGoogle Scholar
Hamburger, P. and Pippert, R. E., ‘Simple, reducible Venn diagrams on five curves and Hamiltonian cycles’, Geom. Dedicata 68 (1997) no. 3, 245–262.CrossRefGoogle Scholar
Hammer, E., Logic and visual information (CSLI Publications, 1995).Google Scholar
Hammer, E. and Danner, N., ‘Towards a model theory of Venn diagrams’, J. Philos. Logic 25 (1996) no. 4, 463–482.CrossRefGoogle Scholar
Hammer, E. and Shin, S. J., ‘Euler’s visual logic’, Hist. Philos. Logic (1998) 1–29.CrossRefGoogle Scholar
Harel, D., ‘On visual formalisms’, Diagrammatic reasoning (eds Glasgow, J., Narayan, N. H. and Chandrasekaran, B.; MIT Press, Cambridge, MA, 1998) 235–271.Google Scholar
Harel, D. and Kahana, H. A., ‘On statecharts with overlapping’, ACM Trans. Softw. Eng. Method 1 (1992) no. 4, 399–421.CrossRefGoogle Scholar
Hegarty, M., ‘Diagrams in the mind and in the world: relations between internal and external visualizations’, Proceedings of 3rd International Conference on the Theory and Application of Diagrams , Lecture Notes in Artificial Intelligence 2980 (Springer, New York, 2004) 1–13.Google Scholar
Howse, J., Molina, F., Shin, S.-J. and Taylor, J., ‘Type-syntax and token-syntax in diagrammatic systems’, Proceedings of 2nd International Conference on Formal Ontology in Information Systems, Maine, USA (ACM Press, New York, 2001) 174–185.Google Scholar
Howse, J., Molina, F., Shin, S.-J. and Taylor, J., ‘On diagram tokens and types’, Proceedings of 2nd International Conference on the Theory and Application of Diagrams, Georgia, USA (Springer, New York, 2002) 146–160. April.Google Scholar
Howse, J., Molina, F., Taylor, J., Kent, S. and Gil, J., ‘Spider diagrams: a diagrammatic reasoning system’, J. Vis. Lang. Comput. 12 (2001) no. 3, 299–324.CrossRefGoogle Scholar
Howse, J. and Schuman, S., ‘Precise visual modelling’, J. Softw. Syst. Model. 4 (2005) 310–325.CrossRefGoogle Scholar
Howse, J., Stapleton, G., Flower, J. and Taylor, J., ‘Corresponding regions in Euler diagrams’, Proceedings of 2nd International Conference on the Theory and Application of Diagrams, Georgia, USA (Springer, New York, 2002) 76–90.Google Scholar
Howse, J., Stapleton, G. and Taylor, J., ‘Spider diagrams’, LMS J. Comput. Math. 8 (2005) 145–194.CrossRefGoogle Scholar
Howse, J., Stapleton, G., Taylor, K. and Chapman, P., ‘Visualizing ontologies: a case study’, The semantic web ISWC 2011 , Lecture Notes in Computer Science 7031 (Springer, New York, 2011) 257–272.CrossRefGoogle Scholar
Jamnik, M., Mathematical reasoning with diagrams (CSLI Press, Stanford, CA, 2001).Google Scholar
Jamnik, M., Bundy, A. and Green, I., ‘Automation of diagrammatic reasoning’, Proceedings of the 15th International Joint Conference on Artificial Intelligence 1 (Morgan Kaufmann Publishers, San Francisco, CA, 1997) 528–533.Google Scholar
Sowa, J. F., Conceptual structures: information processing in mind and machine (Addison-Wesley, Reading, MA, 1984).Google Scholar
John, C., ‘Reasoning with projected contours’, Proceedings of 3rd International Conference on the Theory and Application of Diagrams Lecture Notes in Artificial Intelligence 2980 (Springer, New York, 2004) 147–150.Google Scholar
John, C., ‘Projected contours in Euler diagrams’, Euler diagrams 2004 , Electronic Notes in Theoretical Computer Science 134 (Elsevier, Amsterdam, 2005) 103–126.Google Scholar
John, C., ‘Measuring and reducing clutter in spider diagrams with projections’, PhD Thesis, University of Brighton, 2006.Google Scholar
John, C., Fish, A., Howse, J. and Taylor, J., ‘Exploring the notion of clutter in Euler diagrams’, Proceedings of 4th International Conference on the Theory and Application of Diagrams , Lecture Notes in Artificial Intelligence 4045 (Springer, New York, 2006) 267–282.Google Scholar
Johnson, D. S. and Pollak, H. O., ‘Hypergraph planarity and the complexity of drawing Venn diagrams’, J. Graph Theory 11 (1987) no. 3, 309–325.CrossRefGoogle Scholar
Karnaugh, M., ‘The map method for synthesis of combinational logic circuits’, Trans. Amer. Inst. Electr. Eng. 72 (1953) no. 5, 593–599.Google Scholar
Kent, S., ‘Constraint diagrams: Visualizing invariants in object oriented modelling’, Proceedings of OOPSLA97 (ACM Press, New York, 1997) 327–341.CrossRefGoogle Scholar
Kestler, H., Muller, A., Gress, T. and Buchholz, M., ‘Generalized Venn diagrams: a new method for visualizing complex genetic set relations’, J. Bioinformatics 21 (2005) no. 8, 1592–1595.CrossRefGoogle ScholarPubMed
Kestler, H. A., Müller, A., Kraus, J. M., Buchholz, M., Gress, T. M., Liu, H., Kane, D. W., Zeeberg, B. R. and Weinstein, J., ‘Vennmaster: Area-proportional Euler diagrams for functional GO analysis of microarrays’, BMC Bioinformatics 9 (2008) 67.CrossRefGoogle ScholarPubMed
Larkin, J. and Simon, H., ‘Why a diagram is (sometimes) worth ten thousand words’, J. Cognitive Sci. 11 (1987) 65–99.CrossRefGoogle Scholar
Papadimitriou, C., Grigni, M. and Papadias, D., ‘Topological inference’, 14th Conference on Artificial Intelligence (Morgan Kaufmann, San Francisco, CA, 1995) 901–906.Google Scholar
Mamakani, K., Myrvold, W. and Ruskey, F., ‘Generating simple convex Venn diagrams’, J. Discrete Algorithms 16 (2012) 270–286.CrossRefGoogle Scholar
More, T., ‘On the construction of Venn diagrams’, J. Symbolic Logic 23 (1959) 303–304.CrossRefGoogle Scholar
Riche, N. H. and Dwyer, T., ‘Untangling Euler diagrams’, IEEE Trans. Vis. Comput. Graphics 16 (2010) no. 6, 1090–1099.CrossRefGoogle ScholarPubMed
Ruskey, F. and Weston, M., ‘A survey of Venn diagrams’, Electron. J. Combin. (1997) updated 2001, 2005. www.combinatorics.org/Surveys/ds5/VennEJC.html.Google Scholar
Shimojima, A., ‘Inferential and expressive capacities of graphical representations: survey and some generalizations’, Diagrammatic Representation and Inference: Proceedings of Diagrams 2004 , Lecture Notes in Computer Science 2980 (Springer, New York, 2004) 18–21.CrossRefGoogle Scholar
Shin, S.-J., The logical status of diagrams (Cambridge University Press, Cambridge, 1994).Google Scholar
Simonetto, P., Auber, D. and Archambault, D., ‘Fully automatic visualisation of overlapping sets’, Comput. Graph. Forum 28 (2009) 967–974.CrossRefGoogle Scholar
Stapleton, G. and Delaney, A., ‘Evaluating and generalizing constraint diagrams’, J. Vis. Lang. Comput. 19 (2008) 499–521.CrossRefGoogle Scholar
Stapleton, G., Howse, J., Chapman, P., Delaney, A., Burton, J. and Oliver, I., ‘Formalizing concept diagrams’, 19th International Conference on Distributed Multimedia Systems, Visual Languages and Computing (Knowledge Systems Institute, Skokie, IL, 2013) 182–187.Google Scholar
Stapleton, G., Howse, J. and Rodgers, P., ‘A graph theoretic approach to general Euler diagram drawing’, Theoret. Comput. Sci. 411 (2010) no. 1, 91–112.CrossRefGoogle Scholar
Stapleton, G. and Masthoff, J., ‘Incorporating negation into visual logics: a case study using Euler diagrams’, Visual Languages and Computing 2007 (Knowledge Systems Institute, Skokie, IL, 2007) 187–194.Google Scholar
Stapleton, G., Masthoff, J., Flower, J., Fish, A. and Southern, J., ‘Automated theorem proving in Euler diagrams systems’, J. Automat. Reason. 39 (2007) 431–470.CrossRefGoogle Scholar
Stapleton, G., Thompson, S., Howse, J. and Taylor, J., ‘The expressiveness of spider diagrams’, J. Logic Comput. 14 (2004) no. 6, 857–880.CrossRefGoogle Scholar
Swoboda, N. and Allwein, G., ‘Using DAG transformations to verify Euler/Venn homogeneous and Euler/Venn FOL heterogeneous rules of inference’, J. Softw. Syst. Model. 3 (2004) no. 2, 136–149.CrossRefGoogle Scholar
Thièvre, J., Viaud, M. and Verroust-Blondet, A., ‘Using Euler diagrams in traditional library environments’, Euler Diagrams 2004 , Electronic Notes on Theoretical Computer Science 134 (Elsevier, Amsterdam, 2005) 189–202.Google Scholar
Venn, J., ‘On the diagrammatic and mechanical representation of propositions and reasonings’, Philos. Mag. Ser. 5 10 (1880) 1–18.CrossRefGoogle Scholar
Wilkinson, L., ‘Exact and approximate area-proportional circular Venn and Euler diagrams’, IEEE Trans. Vis. Comput. Graphics 18 (2012) no. 2, 321–331.CrossRefGoogle ScholarPubMed