Generalized constraint diagrams and the classical decision problem

Constraint diagrams are part of the family of visual logics based on Euler diagrams. They have been studied since the 1990s, when they were first proposed by Kent as a means of describing formal constraints within software models. Since that time, constraint diagrams have evolved in a number of ways; a crucial refinement came with the recognition of the need to impose a reading order on the quantifiers represented by diagrammatic syntax. This resulted first in augmented constraint diagrams and, most recently, generalized constraint diagrams (GCDs), which are composed of one or more unitary diagrams in a connected graph. The design of GCDs includes several syntactic features that bring increased expressivity but which also make their metatheory more complex than is the case with preceding constraint diagram notations. In particular, GCDs are given a second order semantics. In this thesis we identify a decidable fragment of GCDs and provide the first set of sound inference rules for the system. We define a particular class of the unitary diagrams drawn from this fragment, which we call gamma-diagrams. We describe a decision procedure for the satisfiability of unitary gamma-diagrams, before developing a means of applying the decision procedure to all unitary diagrams of the fragment, achieved by using the class of gamma-diagrams as a reduction class. Next, we develop a decision procedure for the non-unitary diagrams of the fragment. This procedure makes use of several normal forms which enable us to judge the satisfiability of a (non-unitary) generalized diagram by examining the unitary diagrams it contains. We discuss the ways in which our work is of benefit to users of GCDs and those engaged in making software tools based on them. Finally, we identify the ways in which our results provide the foundations for further theoretical study of the system.