The expressiveness of spider diagrams

Gem Stapleton, John Howse, John Taylor, Simon Thompson

Research output: Contribution to journalArticlepeer-review

Abstract

Spider diagrams are a visual language for expressing logical statements. In this paper we identify a well known fragment of first order predicate logic, that we call MFOL=, equivalent in expressive power to the spider diagram language. The language MFOL= is monadic and includes equality but has no constants or function symbols. To show this equivalence, in one direction, for each diagram we construct a sentence in MFOL= that expresses the same information. For the more challenging converse we prove that there exists a finite set of models for a sentence S that can be used to classify all the models for S. Using these classifying models we show that there is a diagram expressing the same information as S.
Original languageEnglish
Pages (from-to)857-880
Number of pages24
JournalJournal of Logic and Computation
Volume14
Issue number6
DOIs
Publication statusPublished - 1 Dec 2004

Keywords

  • Spider diagrams
  • expressiveness
  • monadic logic
  • model theory

Fingerprint

Dive into the research topics of 'The expressiveness of spider diagrams'. Together they form a unique fingerprint.

Cite this