School of Computing

The expressiveness of spider diagrams augmented with constants

Gem Stapleton, John Taylor, Simon Thompson, and John Howse

Journal of Visual Languages and Computing, 20:182-196, April 2009 [doi].

Abstract

Spider diagrams are a visual language for expressing logical statements or constraints. Several sound and complete spider diagram systems have been developed and it has been shown that they are equivalent in expressive power to monadic first order logic with equality. However, these sound and complete spider diagram systems do not contain syntactic elements analogous to constants in first order predicate logic. We extend the spider diagram language to include constant spiders which represent specific individuals. Formal semantics are given for the extended diagram language. We prove that this extended system is equivalent in expressive power to the language of spider diagrams without constants and, hence, equivalent to monadic first order logic with equality.

Download publication 794 kbytes (PDF)

Bibtex Record

@article{2719,
author = {Gem Stapleton and John Taylor and Simon Thompson and John Howse},
title = {The expressiveness of spider diagrams augmented with constants},
month = {April},
year = {2009},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {10.1016/j.jvlc.2008.01.005},
url = {http://www.cs.kent.ac.uk/pubs/2009/2719},
    publication_type = {article},
    submission_id = {1984_1208264789},
    journal = {Journal of Visual Languages and Computing},
    publisher = {Elsevier},
    volume = {20},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014