This thesis describes original research in the field of knowledge representation and reasoning by presenting novel extensions to the Conceptual Graphs Model, which increase their reasoning capabilities and conceptual modelling applicability in Artificial Intelligence.
Conceptual Graphs benefit from graph-based reasoning mechanisms, plug-in capabilities over existing data structures and good visualization capabilities. These advantages have to be adapted for an information era where quick results and representation versatility are essential for successful frameworks. This thesis will show how to extend Conceptual Graphs as a knowledge representation and reasoning formalism to address these needs. My claim that this extension has to focus on both semantic and syntactic aspects. More precisely, I improve existing reasoning algorithms and propose Conceptual Graphs extensions that allow for the representation of hierarchical knowledge and concurrent, interrelated events. My work is evaluated theoretically. I highlight new polynomial instances for the NP-complete problem of projection checking (the main reasoning mechanism for Conceptual Graphs). I demonstrate the soundness and completeness of my proposed extensions. I show how my extensions can be successfully employed for conceptual modelling.
Department of Computing Science, University of Aberdeen, Aberdeen AB24 3UE, Scotland, UK
phone +44 (0)1224 272295, fax +44 (0)1224 273422
