Spider diagrams of order and a hierarchy of star-free regular languages

Aidan Delaney, John Taylor, Simon Thompson

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBN

Abstract

The spider diagram logic forms a fragment of constraint diagram logic and is 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 logic. 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 denable by spider diagrams of order equipped with the product operator and, based on this relationship, spider diagrams of order are as expressive as rst order monadic logic of order.
Original languageEnglish
Title of host publicationProceedings of the 5th international conference on the theory and application of diagrams
Place of PublicationBerlin Heidelberg
PublisherSpringer-Verlag
Pages172-187
Number of pages16
Volume5223
ISBN (Electronic)9783540877301
ISBN (Print)9783540877295
DOIs
Publication statusPublished - 1 Jan 2008
EventProceedings of the 5th international conference on the theory and application of diagrams - Herrsching, Germany, 19-21 September, 2008
Duration: 1 Jan 2008 → …

Publication series

NameLecture Notes in Computer Science

Conference

ConferenceProceedings of the 5th international conference on the theory and application of diagrams
Period1/01/08 → …

Fingerprint Dive into the research topics of 'Spider diagrams of order and a hierarchy of star-free regular languages'. Together they form a unique fingerprint.

  • Cite this

    Delaney, A., Taylor, J., & Thompson, S. (2008). Spider diagrams of order and a hierarchy of star-free regular languages. In Proceedings of the 5th international conference on the theory and application of diagrams (Vol. 5223, pp. 172-187). (Lecture Notes in Computer Science). Springer-Verlag. https://doi.org/10.1007/978-3-540-87730-1_18