Skip to content

Defining Regular Languages with Diagrams

Bookmark and Share 

Published 01.09.09

Gem Stapleton has been awarded an EPSRC grant for her project Defining Regular Languages with Diagrams.

The proposed research lies at the novel interface of diagrammatic reasoning and formal language theory. Until the very recent work of Gem Stapleton and her collaborators, nobody had observed the strong relationship between diagrammatic logics and formal languages or, therefore, recognized the possible significant benefits of pursuing this line of enquiry. The main aim of the proposed research is to develop a second order diagrammatic logic, capable of defining regular languages. The development of such a logic will be a major step forward for the diagrams community, since the diagrammatic logics that have been formalized and investigated to-date are first order, with the vast majority of them limited to the expressive power of at most monadic first order logic with equality.

The research will develop the novel link between the new second order diagrammatic logic and regular languages. This will not be the first time that regular languages have been related to second order logic, with extensive research conducted into their relationship with symbolic logics. These previous investigations have proved fruitful in terms of our understanding of regular languages, including those that are star-free, and provided insight into the famous star-height problem. However, the syntactic structure of symbolic logic sentences is very different to the manner in which diagrammatic logics make statements. Thus, the development of the proposed diagrammatic logic stands to shed new light on the investigation of regular languages. With the highly significant role that formal language theory plays in computer science, the proposed research stands to bring with it important benefits for this community also.

Royal Statistical Society