A decision procedure for a decidable fragment of generalized constraint diagrams

James Burton, Gem Stapleton, Ali Hamie

Research output: Contribution to journalArticlepeer-review


Constraint diagrams were introduced by Kent, in 1997, as an alternative to the OCL for placing formal constraints on software models. Since their introduction, constraint diagrams have evolved and, after a careful analysis of their positive and negative features, generalized constraint diagrams were proposed. An important benefit of providing a formal model of a software system (diagrammatically or otherwise) is the ability to determine whether that model is consistent (i.e. satisfiable). However, determining satisfiability in an algorithmic, terminating, way is only possible in decidable logics. In this paper, we consider the so-called unitary existential fragment (UEF) of generalized constraint diagrams and, within this fragment, identify a decision procedure for the satisfiability of a particular class of diagrams. We then demonstrate how to extend the decision procedure to the UEF as a whole. This work lays the foundations for providing decision procedures for larger fragments of generalized constraint diagrams and we discuss how this might be achieved in the paper.
Original languageEnglish
Pages (from-to)90-105
Number of pages16
JournalJournal of Visual Languages and Computing
Issue number1
Publication statusPublished - 28 Feb 2011


  • Constraint diagrams
  • Consistency
  • Visual logic
  • Formal diagrammatic reasoning


Dive into the research topics of 'A decision procedure for a decidable fragment of generalized constraint diagrams'. Together they form a unique fingerprint.

Cite this