On the descriptional complexity of a diagrammatic notation

Aidan Delaney; Gem Stapleton

On the descriptional complexity of a diagrammatic notation

Aidan Delaney, Gem Stapleton

University of Brighton

Research output: Chapter in Book/Conference proceeding with ISSN or ISBN › Conference contribution with ISSN or ISBN › peer-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 language	English
Title of host publication	Proceedings of the 13th international conference on Distributed Multimedia Systems
Place of Publication	UT-Dallas, USA
Publisher	Knowledge Systems Institute
Pages	0-0
Number of pages	1
Publication status	Published - 1 Jan 2007
Event	Proceedings of the 13th international conference on Distributed Multimedia Systems - San Francisco, USA, 6-8 September, 2007 Duration: 1 Jan 2007 → …

Conference

Conference	Proceedings of the 13th international conference on Distributed Multimedia Systems
Period	1/01/07 → …

Bibliographical note

Creative Commons Attribution Share-Alike license

Keywords

Spider diagrams
visual languages

Access to Document

VLC07-Delaney.pdfAccepted author manuscript, 237 KBLicence: CC BY

Cite this

@inproceedings{aa7abe1b29b640c1995d04744e0f7f00,

title = "On the descriptional complexity of a diagrammatic notation",

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.",

keywords = "Spider diagrams, visual languages",

author = "Aidan Delaney and Gem Stapleton",

note = "Creative Commons Attribution Share-Alike license; Proceedings of the 13th international conference on Distributed Multimedia Systems ; Conference date: 01-01-2007",

year = "2007",

month = jan,

day = "1",

language = "English",

pages = "0--0",

booktitle = "Proceedings of the 13th international conference on Distributed Multimedia Systems",

publisher = "Knowledge Systems Institute",

}

On the descriptional complexity of a diagrammatic notation. / Delaney, Aidan; Stapleton, Gem.
Proceedings of the 13th international conference on Distributed Multimedia Systems. UT-Dallas, USA: Knowledge Systems Institute, 2007. p. 0-0.

Research output: Chapter in Book/Conference proceeding with ISSN or ISBN › Conference contribution with ISSN or ISBN › peer-review

TY - GEN

T1 - On the descriptional complexity of a diagrammatic notation

AU - Delaney, Aidan

AU - Stapleton, Gem

N1 - Creative Commons Attribution Share-Alike license

PY - 2007/1/1

Y1 - 2007/1/1

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

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

KW - Spider diagrams

KW - visual languages

M3 - Conference contribution with ISSN or ISBN

SP - 0

EP - 0

BT - Proceedings of the 13th international conference on Distributed Multimedia Systems

PB - Knowledge Systems Institute

CY - UT-Dallas, USA

T2 - Proceedings of the 13th international conference on Distributed Multimedia Systems

Y2 - 1 January 2007

ER -

On the descriptional complexity of a diagrammatic notation

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this