On the descriptional complexity of a diagrammatic notation

Aidan Delaney, Gem Stapleton

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBNpeer-review

Abstract

Spider diagrams are a widely studied, visual logic that are able to make statements about relationships between sets and their cardinalities. Various meta-level results for spider diagrams have been established, including their soundness, completeness and expressiveness. In order to further enhance our understanding of spider diagrams, we can compare them with other languages; in the case of this paper we consider star-free regular languages. We establish relationships between various fragments of the spider diagram language and certain well-known subclasses of the star-free regular class. Utilising these relationships, given any spider diagram, we provide an upper-bound on the state complexity of minimal deterministic finite automata corresponding to that spider diagram. We further demonstrate cases where this bound is tight.
Original languageEnglish
Title of host publicationProceedings of the 13th international conference on Distributed Multimedia Systems
Place of PublicationUT-Dallas, USA
PublisherKnowledge Systems Institute
Pages0-0
Number of pages1
Publication statusPublished - 1 Jan 2007
EventProceedings of the 13th international conference on Distributed Multimedia Systems - San Francisco, USA, 6-8 September, 2007
Duration: 1 Jan 2007 → …

Conference

ConferenceProceedings of the 13th international conference on Distributed Multimedia Systems
Period1/01/07 → …

Bibliographical note

Creative Commons Attribution Share-Alike license

Keywords

  • Spider diagrams
  • visual languages

Fingerprint

Dive into the research topics of 'On the descriptional complexity of a diagrammatic notation'. Together they form a unique fingerprint.

Cite this