Skip to search boxSkip to navigationSkip to main content

On the expressiveness of spider diagrams and commutative star-free regular languages

  • Aidan Delaney
    ,
  • Gem Stapleton
    ,
  • John Taylor
    ,
  • Simon Thompson
Research output:
Contribution to journal
Article
Research
Peer-review

About the research

Spider diagrams provide a visual logic to express relations between sets and their elements, extending the expressiveness of Venn diagrams. Sound and complete inference systems for spider diagrams have been developed and it is known that they are equivalent in expressive power to Monadic First-Order Logic with equality, MFOL[=]. In this paper, we further characterize their expressiveness by articulating a link between them and formal languages. First, we establish that spider diagrams define precisely the languages that are finite unions of languages of the form K⊔⊔Γ⁎ where K is a finite commutative language and Γ is a finite set of letters. We note that it was previously established that spider diagrams define commutative star-free languages. As a corollary K⊔⊔Γ⁎ all languages of the form are commutative star-free languages. We further demonstrate that every commutative star-free language is also such a finite union. In summary, we establish that spider diagrams define precisely: (a) languages definable in MFOL[=], (b) the commutative star-free regular languages, and (c) finite unions of the form K⊔⊔Γ⁎ as just described.

Research output information

Output type

Research output:
Contribution to journal
Article
Research
Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 273-288 (16 pages)

Journal (Volume, Issue Number)

Journal of Visual Languages and Computing (Volume 24, Issue 4)

Publication milestones

  • Published - 27/02/2013

Publication status

Published - 27/02/2013

ISSN

1045-926X