Skip to main content

Fragments of Spider Diagrams of Order and their Relative Expressiveness

Delaney, Aidan, Stapleton, Gem, Taylor, John, Thompson, Simon (2010) Fragments of Spider Diagrams of Order and their Relative Expressiveness. In: Goel, Ashok K. and Jamnik, Mateja and Narayanan, N. Hari, eds. Diagrammatic Representation and Inference 6th International Conference, Diagrams 2010. Lecture Notes in Computer Science , 6170. pp. 182-196. Springer (doi:10.1007/978-3-642-14600-8) (KAR id:30645)

Language: English
Download (268kB)
[thumbnail of content.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


Investigating the expressiveness of a diagrammatic logic provides insight into how its syntactic elements interact at the semantic level. Moreover, it allows for comparisons with other notations. Various expressiveness results for diagrammatic logics are known, such as the theorem that Shin's Venn-II system is equivalent to monadic first order logic. The techniques employed by Shin for Venn-II were adapted to allow the expressiveness of Euler diagrams to be investigated. We consider the expressiveness of spider diagrams of order (SDoO), which extend spider diagrams by including syntax that provides ordering information between elements. Fragments of SDoO are created by systematically removing each aspect of the syntax. We establish the relative expressiveness of the various fragments. In particular, one result establishes that spiders are syntactic sugar in any fragment that contains order, negation and shading. We also show that shading is syntactic sugar in any fragment containing negation and spiders. The existence of syntactic redundancy within the spider diagram of order logic is unsurprising however, we find it interesting that spiders or shading are redundant in fragments of the logic. Further expressiveness results are presented throughout the paper. The techniques we employ may well extend to related notations, such as the Euler/Venn logic of Swoboda et al. and Kent's constraint diagrams.

Item Type: Conference or workshop item (UNSPECIFIED)
DOI/Identification number: 10.1007/978-3-642-14600-8
Uncontrolled keywords: determinacy analysis, Craig interpolants
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: S. Thompson
Date Deposited: 21 Sep 2012 09:49 UTC
Last Modified: 16 Nov 2021 10:08 UTC
Resource URI: (The current URI for this page, for reference purposes)
Thompson, Simon:
  • Depositors only (login required):


Downloads per month over past year