This thesis deals with the design and implementation of an object-oriented simulator for conceptual graphs. Conceptual graphs are a means of representing information and knowledge. In particular, they may be used to represent the behavior of mechanisms. Conceptual graph simulation provides the means for verifying that the conceptual graph model of the system is a proper representation of the mechanism. The motivation for the design of this simulator is to help a conceptual graph model designer overcome the imprecision and ambiguity inherent in the English language. When a person translates an English language specification of a system to a conceptual graph model, the model may be incomplete, owing to semantic gaps in the English language specification. The simulator attempts to help the designer fill in these gaps by pointing out missing concepts and relations needed to simulate the model. This thesis covers the issues involved in designing such a simulator, and the implementation of the simulator in Java. The working of the simulator is demonstrated by simulating sample conceptual graphs. Also, a set of action procedures, and a small library of device schema graphs are created, so that devices may be effectively modeled. / Master of Science

No description available.

Les tâches dans les environnements virtuels immersifs sont associées à des techniques et à des dispositifs d’interaction 3D (e.g. la sélection d’objets 3D à l’aide de la main virtuelle via un flystick). Alors que les environnements et les tâches deviennent de plus en plus complexes, les techniques ne peuvent plus être les mêmes pour chaque application, voire pour les différentes situations au sein d’une application. Une solution est d’adapter l’interaction en fonction des besoins de la situation pour améliorer l’utilisabilité. Ces adaptations peuvent être effectuées manuellement par le concepteur ou l’utilisateur, ou automatiquement par le système créant ainsi une interaction adaptative. La formalisation d’une telle assistance automatique nécessite la gestion d’informations pertinentes au vu de la situation. L’ensemble de ces informations fait émerger le contexte de l’interaction. L’assistance adaptative obtenue en raisonnant à partir de ces informations est ainsi consciente du contexte. De nombreuses possibilités existent pour l’obtenir. Notre objectif est une gestion du contexte qui préserve ses degrés élevés d’expressivité et d’évolutivité tout en étant facile à intégrer. Nous proposons une modélisation de ce problème par des graphes conceptuels basés sur une ontologie et gérés par un moteur externe en logique du premier ordre. Le moteur est générique et utilise une base de connaissance contenant des faits et des règles, qui peuvent être changés dynamiquement. Nous avons intégré une notion de confiance, afin d’établir l’adéquation d’une situation à la base de connaissances. La confiance des réactions est comparée à leur impact afin de ne garder que les pertinentes tout en évitant de saturer l’utilisateur. Les applications utilisent des outils qui peuvent être contrôlés par le moteur. Des capteurs permettent d’extraire des informations sémantiques pour le contexte. Des effecteurs permettent d’agir sur l’application et d’obtenir des adaptations. Un jeu d’outils et une base de connaissance pour l’interaction 3D ont été créés. De nombreuses étapes sont introduites dans la base de connaissance pour de bonnes combinaisons et une réflexion indépendante d’outils spécifiques. Nos premières applications illustrent la compréhension de la situation, dont les intérêts et difficultés de l’utilisateur, et le déclenchement d’assistances adaptées. Une étude hors ligne montre ensuite l’accès et l’évolution des étapes du moteur selon la situation. Le raisonnement sémantique générique obtenu est alors expressif, compréhensif, extensif et modifiable dynamiquement. Pour l’interaction 3D, il permet une assistance universelle automatique, ponctuelle ou manuelle à l’utilisateur et des analyses hors-lignes d’activités ou de conceptions pour le concepteur. / Tasks in immersive virtual environments are associated with 3D interaction techniques and devices (e.g. the selection of 3D objects with the virtual hand and a flystick). As environments and tasks become more and more complex, techniques can not remain the same for each application, even for every situations of a single application. A solution is to adapt the interaction depending on the situation in order to increase usability. These adaptations can be done manually by the designer or the user, or automatically by the system thus creating an adaptative interaction. Formalisation of such assistance needs the management of pertinent information regarding the situation. Those items of information make the context emerge from the interaction. The adaptative assistance obtained by reasoning on this information is then context-aware. Numerous possibilities can be used to build one. Our objective is a context management that preserves its high degrees of expressiveness and evolutivity while being easy to plug in. We have built a model for this issue using conceptual graphs based on an ontology and managed externally with a first order logic engine. The engine is generic and uses a knowledge base with facts and rules which can be dynamically changed. We have added a confidence notion, in order to establish a situation similarity to the knowledge base. Reactions’confidences are compared to their impacts so as to keep only the pertinent ones while avoiding user overload. Applications have tools that can be controlled by the engine. Sensors are used to extract semantic information for the context. Effectors are used to act upon the application and to have adaptations. A tools set and a knowledge base have been created for 3D interaction. Numerous steps have been added in the knowledge base to obtain good combinations and a reasoning independent from specific tools. Our first applications shows the situation understanding, including user interests and difficulties, and the triggering of pertinent assistances. An off-line study illustrates the access and evolution of the internal engine steps. The built generic semantic reasoning is expressive, understandable, extensive and modifiable dynamically. For 3D interaction, it allows universal assistances for the user that can be automatic, punctual or manual and off-line activities or conceptions analysis fort he designers.

Aus der Einleitung: 'Conceptual graphs (CGs) are an expressive formalism for representing knowledge about an application domain in a graphical way. Since CGs can express all of first-order predicate logic (FO), they can also be seen as a graphical notation for FO formulae. In knowledge representation, one is usually not only interested in representing knowledge, one also wants to reason about the represented knowledge. For CGs, one is, for example, interested in validity of a given graph, and in the question whether one graph subsumes another one. Because of the expressiveness of the CG formalism, these reasoning problems are undecidable for general CGs. In the literature [Sow84, Wer95, KS97] one can find complete calculi for validity of CGs, but implementations of these calculi have the same problems as theorem provers for FO: they may not terminate for formulae that are not valid, and they are very ineficient. To overcome this problem, one can either employ incomplete reasoners, or try to find decidable (or even tractable) fragments of the formalism. This paper investigates the second alternative. The most prominent decidable fragment of CGs is the class of simple conceptual graphs (SGs), which corresponds to the conjunctive, positive, and existential fragment of FO (i.e., existentially quantified conjunctions of atoms). Even for this simple fragment, however, subsumption is still an NP-complete problem [CM92]. SGs that are trees provide for a tractable fragment of SGs, i.e., a class of simple conceptual graphs for which subsumption can be decided in polynomial time [MC93]. In this report, we will identify a tractable fragment of SGs that is larger than the class of trees. Instead of trying to prove new decidability or tractability results for CGs from scratch, our idea was to transfer decidability results from description logics [DLNN97, DLNS96] to CGs. The goal was to obtain a \natural' sub-class of the class of all CGs in the sense that, on the one hand, this sub-class is defined directly by syntactic restrictions on the graphs, and not by conditions on the first-order formulae obtained by translating CGs into FO, and, on the other hand, is in some sense equivalent to a more or less expressive description logic. Although description logics (DLs) and CGs are employed in very similar applications (e.g., for representing the semantics of natural language sentences), it turned out that these two formalisms are quite different for several reasons: (1) conceptual graphs are interpreted as closed FO formulae, whereas DL concept descriptions are interpreted by formulae with one free variable; (2) DLs do not allow for relations of arity > 2 ; (3) SGs are interpreted by existential sentences, whereas almost all DLs considered in the literature allow for universal quantification; (4) because DLs use a variable-free syntax, certain identifications of variables expressed by cycles in SGs and by co-reference links in CGs cannot be expressed in DLs. As a consequence of these differences, we could not identify a natural fragment of CGs corresponding to an expressive DL whose decidability was already shown in the literature. We could, however, obtain a new tractability result for a DL corresponding to SGs that are trees. This correspondence result strictly extends the one in [CF98]. In addition, we have extended the tractability result from SGs that are trees to SGs that can be transformed into trees using a certain \cycle-cutting' operation. The report is structured as follows. We first introduce the description logic for which we will identify a subclass of equivalent SGs. In Section 3, we recall basic definitions and results on SGs. Thereafter, we introduce a syntactical variant of SGs which allows for directly encoding the support into the graphs (Section 4.1). In order to formalize the equivalence between DLs and SGs, we have to consider SGs with one distinguished node called root (Section 4.2). In Section 5, we finally identify a class of SGs corresponding to a DL that is a strict extension of the DL considered in [CF98].

In the research of the business IS development the business rules approach has achieved a lot of attention and already has a steady niche with a strong motivation behind. The usefulness of the approach and its advantages over the traditional IS development approaches call for the technology standards. Despite the work done towards standardization there is still a way to go – commercial products use their unique modeling languages for business rules, most of their rules processing and enforcement engines are stand-alone, even the embeddable ones use their unique rules representation format. In our research focusing on the business rules we have stepped towards employing the widely spread technology of active databases and have argued that it is feasible and possible to model business rules using conceptual graphs. Such a model having representations in visual and textual form (linear form and CGIF) and the possibility to translate the model to the near natural English language can be used both at conceptual and implementation levels. We have designed and implemented the automatic trigger generation component. Using the representative example from the real business organization (the representative example was comprised of structural domain knowledge and corresponding business rules) we have carried out the experiment during which the business rules model was transformed from visual notation to CGIF, then from CGIF to XML, and then from XML to MS SQL Server trigger. The... [to full text]

In the research of the business IS development the business rules approach has achieved a lot of attention and already has a steady niche with a strong motivation behind. The usefulness of the approach and its advantages over the traditional IS development approaches call for the technology standards. Despite the work done towards standardization there is still a way to go – commercial products use their unique modeling languages for business rules, most of their rules processing and enforcement engines are stand-alone, even the embeddable ones use their unique rules representation format. In our research focusing on the business rules we have stepped towards employing the widely spread technology of active databases and have argued that it is feasible and possible to model business rules using conceptual graphs. Such a model having representations in visual and textual form (linear form and CGIF) and the possibility to translate the model to the near natural English language can be used both at conceptual and implementation levels. We have designed and implemented the automatic trigger generation component. Using the representative example from the real business organization (the representative example was comprised of structural domain knowledge and corresponding business rules) we have carried out the experiment during which the business rules model was transformed from visual notation to CGIF, then from CGIF to XML, and then from XML to MS SQL Server trigger. The... [to full text]

The thesis describes a rational reconstruction of Sowa's theory of Conceptual Graphs. The reconstruction produces a theory with a firmer logical foundation than was previously the case and which is suitable for computation whilst retaining the expressiveness of the original theory. Also, several areas of incompleteness are addressed. These mainly concern the scope of operations on conceptual graphs of different types but include extensions for logics of higher orders than first order. An important innovation is the placing of negation onto a sound representational basis. A comparison of theorem proving techniques is made from which the principles of theorem proving in Peirce logic are identified. As a result, a set of derived inference rules, suitable for a goal driven approach to theorem proving, is developed from Peirce's beta rules. These derived rules, the first of their kind for Peirce logic and conceptual graphs, allow the development of a novel theorem proving approach which has some similarities to a combined semantic tableau and resolution methodology. With this methodology it is shown that a logically complete yet tractable system is possible. An important result is the identification of domain independent heuristics which follow directly from the methodology. In addition to the theorem prover, an efficient system for the detection of selectional constraint violations is developed. The proof techniques are used to build a working knowledge base system in Prolog which can accept arbitrary statements represented by conceptual graphs and test their semantic and logical consistency against a dynamic knowledge base. The same proof techniques are used to find solutions to arbitrary queries. Since the system is logically complete it can maintain the integrity of its knowledge base and answer queries in a fully automated manner. Thus the system is completely declarative and does not require any programming whatever by a user with the result that all interaction with a user is conversational. Finally, the system is compared with other theorem proving systems which are based upon Conceptual Graphs and conclusions about the effectiveness of the methodology are drawn.

Conceptual graphs (CGs) are an expressive and intuitive formalism, which plays an important role in the area of knowledge representation. Due to their expressiveness, most interesting problems for CGs are inherently undecidable. We identify the syntactically defined guarded fragment of CGs, for which both subsumption and validity is decidable in deterministic exponential time.

Situation awareness and collective intelligence are two technologies used in smart systems. The former renders those systems able to reason upon their abstract knowledge of what is going on. The latter enables them learning and deriving new information from a composition of experiences of their users. In this dissertation we present a doctoral research on an attempt to combine the two in order to obtain, in a collaborative fashion, situation-based rules that the whole community of entities would benefit of sharing. We introduce the KRAMER recommendation system, which we designed and implemented as a solution to the problem of not having decision support tools both situation-aware and collaborative. The system is independent from any domain of application in particular, in other words generic, and we apply its prototype implementation to context-enriched social communication scenario.