School of Computing

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

Aidan Delaney, John Taylor, and Simon Thompson

In Gem Stapleton, John Howse, and John Lee, editors, Diagrammatic Representation and Inference: 5th International Conference, Diagrams 2008, Herrsching, Germany, September 19-21, 2008, number 5223 in Lecture Notes in Computer Science, pages 182-196, September 2008 [doi].

Abstract

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.

Download publication 369 kbytes (PDF)

Bibtex Record

@inproceedings{2812,
author = {Aidan Delaney and John Taylor and Simon Thompson},
title = {{Spider Diagrams of Order and a Hierarchy of Star-Free Regular Languages}},
month = {September},
year = {2008},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {10.1007/978-3-540-87730-1_18},
url = {http://www.cs.kent.ac.uk/pubs/2008/2812},
    publication_type = {inproceedings},
    submission_id = {1604_1222315261},
    ISBN = {978-3-540-87729-5},
    booktitle = {Diagrammatic Representation and Inference: 5th International Conference, Diagrams 2008, Herrsching, Germany, September 19-21, 2008},
    editor = {Gem Stapleton and John Howse and John Lee},
    number = {5223},
    series = {Lecture Notes in Computer Science},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014