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

Aidan Delaney, Gem Stapleton, John Taylor, Simon Thompson

Research output: Contribution to journalArticle

Abstract

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.
Original languageEnglish
Pages (from-to)273-288
Number of pages16
JournalJournal of Visual Languages and Computing
Volume24
Issue number4
DOIs
Publication statusPublished - 27 Feb 2013

Fingerprint

Spiders
Regular Languages
Expressiveness
Star
Diagram
Union
Venn diagram
Language
Formal Languages
Expressive Power
First-order Logic
Finite Set
Corollary
Equality
Express
Logic

Keywords

  • Spider diagrams
  • Diagrammatic logics
  • Regular languages
  • Expressiveness
  • Star-free languages

Cite this

Delaney, Aidan ; Stapleton, Gem ; Taylor, John ; Thompson, Simon. / On the expressiveness of spider diagrams and commutative star-free regular languages. In: Journal of Visual Languages and Computing. 2013 ; Vol. 24, No. 4. pp. 273-288.
@article{a42c25e22ef84f4bbfa9f9ebf2ff5bb0,
title = "On the expressiveness of spider diagrams and commutative star-free regular languages",
abstract = "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.",
keywords = "Spider diagrams, Diagrammatic logics, Regular languages, Expressiveness, Star-free languages",
author = "Aidan Delaney and Gem Stapleton and John Taylor and Simon Thompson",
year = "2013",
month = "2",
day = "27",
doi = "10.1016/j.jvlc.2013.02.001",
language = "English",
volume = "24",
pages = "273--288",
journal = "Journal of Visual Languages and Computing",
issn = "1045-926X",
number = "4",

}

On the expressiveness of spider diagrams and commutative star-free regular languages. / Delaney, Aidan; Stapleton, Gem; Taylor, John; Thompson, Simon.

In: Journal of Visual Languages and Computing, Vol. 24, No. 4, 27.02.2013, p. 273-288.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Delaney, Aidan

AU - Stapleton, Gem

AU - Taylor, John

AU - Thompson, Simon

PY - 2013/2/27

Y1 - 2013/2/27

N2 - 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.

AB - 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.

KW - Spider diagrams

KW - Diagrammatic logics

KW - Regular languages

KW - Expressiveness

KW - Star-free languages

U2 - 10.1016/j.jvlc.2013.02.001

DO - 10.1016/j.jvlc.2013.02.001

M3 - Article

VL - 24

SP - 273

EP - 288

JO - Journal of Visual Languages and Computing

JF - Journal of Visual Languages and Computing

SN - 1045-926X

IS - 4

ER -