Skip to main content

Spider Diagrams of Order and a Hierarchy of Star-Free Regular Languages

Delaney, Aidan and Taylor, John and Thompson, Simon (2008) Spider Diagrams of Order and a Hierarchy of Star-Free Regular Languages. In: Stapleton, Gem and Howse, John and Lee, John, eds. Diagrammatic Representation and Inference 5th International Conference. Lecture Notes in Computer Science . Springer, Berlin, Germany, pp. 172-187. ISBN 978-3-540-87729-5. E-ISBN 978-3-540-87730-1. (doi:10.1007/978-3-540-87730-1_18) (KAR id:24010)

Language: English
Click to download this file (378kB)
[thumbnail of SpiderThompson.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


The spider diagram logic forms a fragment of the constraint diagram logic and was designed to be primarily used as a diagrammatic software specification tool. Our interest is in using the logical basis of spider diagrams and the existing known equivalences between certain logics, formal language theory classes and some automata to inform the development of diagrammatic logics. Such developments could have many advantages, one of which would be aiding software engineers who are familiar with formal languages and automata to more intuitively understand diagrammatic logics. In this paper we consider relationships between spider diagrams of order (an extension of spider diagrams) and the star-free subset of regular languages. We extend the concept of the language of a spider diagram to encompass languages over arbitrary alphabets. Furthermore, the product of spider diagrams is introduced. This operator is the diagrammatic analogue of language concatenation. We establish that star-free languages are definable by spider diagrams of order equipped with the product operator and, based on this relationship, spider diagrams of order are as expressive as first order monadic logic of order.

Item Type: Book section
DOI/Identification number: 10.1007/978-3-540-87730-1_18
Uncontrolled keywords: Spider Diagram, Order, reasoning, Hierarchy, Star-Free, Regular, Languages
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 29 Mar 2010 12:10 UTC
Last Modified: 16 Nov 2021 10:02 UTC
Resource URI: (The current URI for this page, for reference purposes)
Thompson, Simon:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.