| Abstract | The conceptual graph formalism of John Sowa forms a system of order-sorted logic based on Charles Peirce‘s existential graphs. Since its introduction, the conceptual graph theory has been used in a wide variety of areas including knowledge representation, database inference, natural language semantics, automated deduction and reasoning, situation and discourse theory, data modeling, knowledge acquisition and knowledge engineering, and deductive and object-oriented systems. Besides, conceptual graphs are proposed as a normative language for conceptual schemas by the ANSI standards committee on Information Resource Dictionary Systems, and as a presentation language for knowledge in conceptual models by the ANSI standards committee on Information Processing Systems. Logic is a direct or indirect basis of most of these areas of applications. All of these interests in conceptual graphs call for a formal computational framework for conceptual graph theory with a well defined semantics. Although, in his original theory. John Sowa neatly addressed most of the basic philosophical and logical issues, those are not sufficient for using conceptual graphs as a formal computational framework based on logic. This is one of the central issues that are addressed in this dissertation. The conceptual graph formalism is general enough to allow logical statements in propo- sitional, first-order, higher-order, and modal logic. However, in this dissertation we only consider the first-order subset of conceptual graphs. At first, all the basic elements of the conceptual graph theory are formally specified from the view point of logic and computation. Many of the existing notions are extended and formalized, and a number of new notions and concepts are developed. These result in the specification of an order-sorted logic programming language based on conceptual graphs, called the conceptual graph language or CG L. Then we extend the basic conceptual graph language mainly focusing on its ability in modeling nested information and complex objects in a logical framework. We also adopt a meta-level of representation, resulting in a two-level order-sorted language of logic and information. Next, the interpretation structure for the language and necessary notions of interpre- tations, models, and truth evaluation for statements in CGL are formally defined. It is observed that in CGL, the t0pology of the assertions and the type hierarchies play impor- tant role in determining meaning of various forms of assertions. Accordingly, a notion of conceptual graph subsumption is defined. A few other useful structures and relations are de— fined that are used in defining a model theoretic interpretation of conceptual graph programs. These include: the G-sets, three unique but equivalence representations of G-sets, and three equivalence transformations of G-sets. Moreover, a fiXpoint theory with conceptual graph subsumption is developed and a fixpoint semantics is defined in terms of the newly defined immediate consequence operator with subsumption. Then the procedural semantics of the conceptual graph programs is specifier] in terms of two proof procedures: a resolution-based refutation procedure called CGA resolution, and a direct derivation proof procedure called COD—derivation. Both the procedures make use of a. set of extended inference rules, and a newly defined conceptual graph unification procedure. Further, the unification procedure is extended to be a parameterized one, so that some control [Illl information can be passed to the procedure for using different graph matching options. It is proved that both the procedures are sound and complete with respect to the declarative semantics. The conceptual graph language is formally specified as a generic language that effec— tively represents a class of languages indexed by its concept universe, that contains a set of domain-independent constructs. In aspecific instance of the language, the domain-dependent constructs are declared and defined as appropriate for a particular domain of application. in the later part of the dissertation, a semi-specific language is presented as an example of ap- plications of CGL. The CG language, called GiSIT, is intended to be used for situation theoretic programming. The major results of this dissertation include the devel0pment ol' the declarative semantics of the conceptual graph language that provides a sound basis for understanding the behavior of any program or model in the language, the procedural semantics that is formally sound and complete, a situation theoretic programming environment, and an ontology in the language demonstrating how it may be useful in data modeling and may possibly be extended towards a design and specification language for knowledge baSes. Although, these results show the flexibility and expressive power of CGL that should be u5el'ul in problem solving in many areas of natural language processing and artificial intelligence, the absence of sound tool is a major hurdle towards its practical applications. Nevertheless, the results of this dissertation should usefully complement other efforts in implementing a sound system of conceptual graphs. |