Skip to main content

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

Delaney, Aidan, Stapleton, Gem, Taylor, John, Thompson, Simon (2013) On the expressiveness of spider diagrams and commutative star-free regular languages. Journal of Visual Languages and Computing, 24 (4). pp. 273-288. ISSN 1045-926X. (doi:10.1016/j.jvlc.2013.02.001) (KAR id:33572)

PDF
Language: English
Download (810kB) Preview
[thumbnail of main.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:
http://dx.doi.org/10.1016/j.jvlc.2013.02.001

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 {black small square} ?*, 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, all languages of the form K {black small square} ?* 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 {black small square} ?*, as just described.

Item Type: Article
DOI/Identification number: 10.1016/j.jvlc.2013.02.001
Subjects: Q Science > QA Mathematics (inc Computing science)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: S. Thompson
Date Deposited: 11 Apr 2013 15:38 UTC
Last Modified: 16 Nov 2021 10:11 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/33572 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year