Whole Structure, Its Representation And Reasoning

The process applying computer to solve an application problem can be summarized as using language and Ontology to build computable models of the domain for certain purpose. This process involves at least three main fields, namely, Ontology, logic and computation. Among them, Ontology is the kernel and start point. The work of this thesis is divided into three parts according to the three fields.1 The work related to OntologyBased on the detailed discussion and analysis on Part-Whole relationship (partof), this thesis presents the construct named whole structure. Part-Whole relation has caused considerable attention due to its special semantics and important status in Ontology. Firstly, it is shown that the representation of whole with partof is a rather complex, difficult and error-prone task. The main reason is that the special semantics of partof is ignored in these representations. Based on the deep analysis, it is revealed that partof is the specialization of in relation and its special semantics lies in ontological dependence and unity. Further, it is pointed out that this special semantics can not be captured by the current formal languages in a natural way. To overcome this problem, whole structure, a construct with very strong ontology power, is introduced. By it, a whole is represented as a structured thing which is comprised of some internal things. In this kind of representations, the special semantics of partof and in relation can be directly expressed by whole structure and its internal things. Because the whole structure possesses inherent modularity and local semantics, the representation is very natural and simple.Based on the whole structure, a general role model is given. Role is another notion received considerable attention. Furthermore, roles are crucial to the representation of wholes. The related work has shown that role is a very important and fundamental notion and its semantics is tied up with object and context. To formalize the role, we should formalize the context first. Because the whole structure is essentially a formal construct corresponding to context, it can be used to formalize the primary characteristics of roles. The result is a novel role model. In this model, roles are explicitly distinguished from objects but always played by objects; roles are always internal to some whole structure; roles are existentially dependent on their players and contexts they reside in. This model is very simple and general to capture almost all characteristics of roles. Based on the research of Ontology in philosophy, an ontological metamodeling architecture (OMMA) is proposed. In philosophy, Ontology consists of at least three main parts: a list of basic categories, the properties of these categories and the basic relations between them, a metaphysics framework for explaining these categories. There are also two principles, i.e., the three levels instantiation structure and Peirce's trichotomy reflect some basic ideas underpinning Ontology. Base on these principles, this thesis present OMMA and a general pattern for representing being. This pattern reveals that the main task in the each level of OMMA is to construct the dependence relations among being by whole structure. This architecture serves as the foundation for defining formal theory, ontology language and metalanguage in this thesis.2 The work related to logic languageBased on OMMA, a novel ontology language is presented which can be viewed as the extension of the traditional language with whole structure.In this language, whole structure is an inherent syntax element, and thus the syntax and semantics are both changed greatly. In syntax, it is regulated that when referring internal elements they must be accompanied with their whole structure (context). This kind of concepts (instances) are called concrete concepts (instances). In semantics, set theory alone is not enough. A new formal theory is proposed by extending set theory with in relation and intension structure. In other words, in relation is endowed with the same fundamental status as instantiation.With this language, several important relations such as Is-A, play and ontological dependence are formally defined. Especially, roles are also formally characterized. Further, two kinds of semantics are proposed based on two different views on role instances.This language is applied to the formalization of UML static diagrams. The representation with UML is not strict enough to gain its formal semantics based on the presented language. So, the primary task is to give formal specifications to the main UML modeling elements. For this, a new framework for formalizing UML static diagrams is presented and it can be viewed as a specialization of the proposed OMMA. Further, several basic constructs of UML are formally defined within this framework. Base on them, the representation of UML becomes more strick and they can be easily transformed into the language presented in this thesis. Furthermore, the separated models for modeling different aspects can be fused together in an inherent way. 3 The work related to the extension of Description Logics with whole structureDescription Logics (DLs) are one of the most important knowledge representation formalism. They emphasize on the inclusion relation between concepts and provide sound and complete reasoning services for key reasoning problems. The main work in this part is to present a decidable and more power language by extending DLs with whole structure. This result is attributed to the properties of the model theory resulted from whole structure.Two decidable extensions of DLs with relation restrictions in different ways are given. The first one adopts whole structure to represent relations. Because of the inherent modularity of whole structure, the restrictions related to the same relation can be compactly organized together. By this, n-arity relations can be represented in a natural way and the efficiency of reasoning algorithm can also be improved. The other one extends DLs with acyclic and finite chain relation restrictions, which can capture the constraints of directed acyclic relations and well-founded property. Both of the two extentions are decidable.The second contribution of this part is to establish the finite model reasoning algorithms (FMRA) of DLs with or without cardinality restrictions (called CBox also) respectively based on integer programming. The finite model restriction is crucial to the satisfiability of concepts with whole structure.Based on the detailed analysis, the main difficulty in the FMRA of DLs without cardinality restrictions is pointed out. To tackle it, the notion of qualified subtype is introduced. With this notion, several FMRA in different DLs are presented. They are more simple and practical than the ones proposed in the related work. For the FMRA of DLs with CBox, the analysis of their computation complexities reveals that the reasoning in the basic description logic ALC w.r.t. CBox is NExpTime-complete. This means that the reasoning in DLs w.r.t. CBox is commonly difficult. Further, the key difference on FMRAs between the DLs with CBox and the ones without CBox is analyzed. Several practical algorithms with tight upper bound complexity for the DLs with CBox are presented. To the best of my knowledge, this is the first practical finite model decision procedure for DLs with CBox.At last, this thesis presents a formal language by extending the DL ALCIQ with whole structure. Its sound and complete algorithm is also given. Essentially, this algorithm is a hybrid of tableau algorithm with FMRA where the later is used to decide the satisfiability of whole structure. It is shown that this language can significantly improve the expressivity of DLs.The main contribution of this thesis can be summarized as a good ontology base has great influence on the formal theory and languages, and the later further impact the com-putability of their restricted sublanguages. Several creative contributions are made among three main fields. It is hoped that the results of this thesis can help the establishment of the more powerful foundation, and can also help to provide the more nature, simple and powerful languages for other fields such as software engineering.