Search

We consider the deduction problem in the existential conjunctive fragment of first-order logic with atomic negation. This problem can be recast in terms of other database and artificial intelligence problems, namely query containment, clause entailment and boolean query answering. We refine an algorithm scheme that was proposed for query containment, which itself improves other known algorithms in databases. To study it experimentally, we build a random generator and analyze the influence of several parameters on the problem instance difficulty. Using this methodology, we experimentally compare several heuristics. [ABSTRACT FROM AUTHOR]

We consider the containment problem for conjunctive queries with atomic negation. Firstly, we refine an existing algorithm based on homomorphism checks, which itself improves other known algorithms in databases, and analyze it experimentally. Secondly, we present a new algorithm based on the translation of the containment problem into the problem of checking the unsatisfiability of a propositional logical formula, which allows us to use a SAT solver, and we experimentally compare both algorithms. [ABSTRACT FROM AUTHOR]

Though similarities between the Semantic Web language RDF(S) and languages of the Conceptual Graphs family have often been pointed out, the differences between these formalisms have been a source of difficulties while trying to translate objets of a language into the other. In this paper, we present two such transformations, that have been implemented into the CoGUI platform, and discuss their respective strengths and weaknesses. [ABSTRACT FROM AUTHOR]

This paper is an extended abstract of the talk given at ICCS΄09. Rules have long been considered as an essential component of knowledge-based systems. We focus here on conceptual graph rules and on the semantically equivalent knowledge constructs in logic and databases, namely rules with existential variables and tuple-generating dependencies. The aim of this presentation is to synthesize main decidability, complexity and algorithmic results obtained on this kind of rules. We emphasize the fact that the graph vision of rules has led to new results. [ABSTRACT FROM AUTHOR]

The performance of interferometric instruments is strongly linked to the quality of piston stabilization. Next generation VLTI instruments plan to use 4to8 beams simultaneously. In the current VLTI implementation, the maximum number of beams that can be phased using FINITO and PRIMA/FSU simultaneously is5. Therefore, a new fringe sensor is required for the VLTI. When cophasing a large number of beams, other approachs than the classical complex pairwise combination should be considered. Focal-plane wavefront sensing allows the cophasing of a large number of beams with a very simple opto-mechanical device and can also measure high-order modes, such as tip/tilt/defocus/... This solution has been selected in other projects such as DARWIN or Earth observation. Experimental results, obtained with a laboratory breadboard tested on the BRISE bench at ONERA, confirm the validity of this approach for nanometric measurements and make such a simple fringe sensor an attractive component for the 2nd generation VLTI [ABSTRACT FROM AUTHOR]

Griwes is an initiative to develop a common model and an open-source freeware platform shared by different graph-based frameworks. We provide an overview of its objectives, architecture and specifications. We detail some of the basic mathematical structures that are used to characterize the primitives for graph-based knowledge representation. We then propose to factorize recurrent knowledge representation primitives that can be shared across specific graph-based languages and we provide a proof of concept by showing how two languages (Simple Conceptual Graphs and RDF) can be described in this framework. [ABSTRACT FROM AUTHOR]

Polarized conceptual graphs (PGs) are simple conceptual graphs added with a restricted form of negation, namely negation on relations. Classical deduction with PGs (in short PG-Deduction) is highly intractable; it is indeed ]> complete. In [LM06] a brute-force algorithm for solving PG-Deduction was outlined. In the present paper, we extend previous work with two kinds of results. First, we exhibit particular cases of PGs for which the complexity of PG-Deduction decreases and becomes not more difficult than in simple conceptual graphs. Secondly, we improve the brute-force algorithm with several kinds of techniques based on properties concerning the graph structure and the labels. [ABSTRACT FROM AUTHOR]

Query containment is a fundamental problem of databases. Given two queries q1 and q2, it asks whether the set of answers to q1 is included in the set of answers to q2 for any database. In this paper, we investigate this problem for conjunctive queries with negated subgoals. We use graph homomorphism as the core notion, which leads us to extend the results presented in [Ull97] and [WL03]. First, we exhibit sufficient (but not necessary) conditions for query containment based on special subgraphs of q2, which generalize that proposed in [WL03]. As a corollary, we obtain a case where the time complexity of the problem decreases. From a practical viewpoint, these properties can be exploited in algorithms, as shown in the paper. Second, we propose an algorithm based on the exploration of a space of graphs, which improves existing algorithms. [ABSTRACT FROM AUTHOR]

This paper studies the introduction of atomic negation into simple conceptual graphs. Several semantics of negation are explored w.r.t. the deduction problem and the query answering problem. Sound and complete algorithm schemes based on projection (or coref-projection) are provided in all cases. The processing of equality/inequality is added to the framework. [ABSTRACT FROM AUTHOR]

Description Logics (DLs) are a family of class based knowledge representation formalisms characterised by the use of various constructors to build complex classes from simpler ones, and by an emphasis on the provision of sound, complete and (empirically) tractable reasoning services. They have a range of applications, but are mostly widely known as the basis for ontology languages such as OWL. The increasing use of DL based ontologies in areas such as e-Science and the Semantic Web is, however, already stretching the capabilities of existing DL systems, and brings with it a range of challenges for future research. [ABSTRACT FROM AUTHOR]

C. S. Peirce's research into a possible applied science of whatever might be trichotomically analyzed has here been developed as trikonic - that is, diagrammatic trichotomic. Such a science (and its proposed adjunct tool) may have significant implications for the work of testbed collaboratories and other virtual communities concerned with pragmatically directed inquiry and knowledge representation. [ABSTRACT FROM AUTHOR]

A key purpose of Multi-Agent Systems (MAS) is to assist humans make better decisions given the vast and disparate information that global systems such as the Web have enabled. The resulting popularity of Agent-Oriented Software Engineering (AOSE) thus demands a methodology that facilitates the development of robust, scalable MAS implementations that recognise real-world semantics. Using an exemplar in the Community Healthcare domain and Conceptual Graphs (CG), we describe an AOSE approach that elicits the hitherto hidden requirements of a system much earlier in the software development lifecycle, whilst also incorporating model-checking to ensure robustness. The resulting output is then available for translation into Agent Oriented Unified Modelling Language (AUML) and further developed using the agent development toolkit of choice. [ABSTRACT FROM AUTHOR]

Ontology as the study of being as such dates back to ancient Greek philosophy, but the term itself was coined in the early 17th century. The idea termed in this manner was further studied within academic circles of the Protestant Enlightenment. In this tradition it was generally believed that ontology is supposed to make true statements about the conceptual structure of reality. A few decades ago computer science imported and since then further elaborated the idea of ‘ontology' from philosophy. Here, however, the understanding of ontology as a collection of true statements has often been played down. In the present paper we intend to discuss some significant aspects of the notion of ‘ontology' in philosophy and computer science. Mainly we focus on the questions: To what extent are computer scientists and philosophers — who all claim to be working with ontology problems — in fact dealing with the same problems? To what extent may the two groups of researchers benefit from each other? It is argued that the well-known philosophical idea of ontological commitment should be generally accepted in computer science ontology. [ABSTRACT FROM AUTHOR]

After noting that informal documents and formal knowledge bases are far from ideal for discussing or retrieving technical knowledge, we propose mechanisms to support the sharing, re-use and cooperative update of semi-formal semantic networks, assign values to contributions and credits to the contributors. We then propose ontological elements to guide and normalize the construction of such knowledge repositories, and an approach to permit the comparison of tools or techniques. [ABSTRACT FROM AUTHOR]

Google's project to digitize five of the world's greatest libraries will dramatically extend their search engine reach in the future. Current search-engine philosophy, which asserts that "any search starts with a question to be answered," will need to be advanced in terms of Peirce's philosophy: "Any inquiry begins by creating an hypothesis to be tested, or with abduction." As conceptual structures researchers prepare to meet access challenges in the world of large Internet knowledge stores, they have a solid foundation in Peirce's theorized stages of inquiry: abduction, deduction, and induction. To indicate how conceptual structures tools must augment collaborative, Internet-based inquiry, we imagine a future scenario in the context of a user-centered testbed, where Peirce scholars apply Peirce's pragmatic theory in their complex manuscript reconstruction work. We suggest that games of inquiry can be developed to formalize user collaboration and technology needs, for improved specification of tool requirements in the testbed context. [ABSTRACT FROM AUTHOR]

Ontologies, taxonomies, and other semantic hierarchies are increasingly necessary for organizing large quantities of data. We continue our development of knowledge discovery techniques based on combinatorial algorithms rooted in order theory by aiming to supplement the pseudo-distances previously developed as structural measures of vertical height in poset-based ontologies with quantitative measures of vertical distance based on additional statistical information. In this way, we seek to accommodate weighting of different portions of the underlying ontology according to this external information source. We also wish to improve on the deficiencies of existing such measures, in particular Resnik's measure of semantic similarity in lexical databases such as Wordnet. We begin by recalling and developing some basic concepts for ordered data objects, including our pseudo-distances and the operation of probability distributions as weights on posets. We then discuss and critique Resnik's measure before introducing our own sense of links weights and weighted normalized pseudo-distances among comparable nodes. [ABSTRACT FROM AUTHOR]

This paper overviews and analyses the on-going research attempts to apply language technologies to automatic ontology acquisition. At first glance there are many successful approaches in this very hot field. However, most of them aim at the extraction of named entities as well as draft taxonomies and partonomies. Only few attempts exist for enriching ontologies by applying word-sense disambiguation. There are principle obstacles to extract automatically coherent conceptualisations from raw texts: it is impossible to identify exactly the types and their instances as well as the word meanings which denote types. It is also impossible to validate a text-based conceptual model against the real world. Thus we can expect only partial success in the semi-automatic acquisition in specific (limited) domains, by workbenches supporting the human knowledge engineer in the final ontological choices. Keywords: natural language processing, information extraction, automatic knowledge acquisition from text [ABSTRACT FROM AUTHOR]

We present a new method for graphically interrogating and checking UML class diagrams. We employ the model of conceptual graphs (CGs) as representation, calculation and visualisation model. The key idea of our work is to translate UML class diagrams into the formalism of CGs. First, UML notations are encoded into UML Ontology that is a support of CG. Second, using the UML Ontology, a UML class diagram can be translated into a CG, called CG class diagram. Third, CG class diagrams can be interrogated via the elementary operation of CG, named projection. Fourth, constraints and rules provides a way to model specifications for checking CG class diagrams. We use two approaches to check a class diagram: object-oriented specifications and field specifications. [ABSTRACT FROM AUTHOR]

In his grammar of ancient Sanskrit, Pāṇini represents the phonological classes as intervals of a list. This representation method and especially the actual list constructed by Pāṇini, which is called the Śivasūtras, earns universal admiration. The legend says that god Śiva revealed the Śivasūtras to Pāṇini in order to let him start developing his grammar of Sanskrit. A question still discussed is whether it is possible to shorten the Śivasūtras. In the course of this paper, I am going to prove that this question can be reduced to a question about the graph-theoretical form of a particular formal concept lattice. Furthermore, I show how the Śivasūtras can be reconstructed from Pāṇini's grammar. [ABSTRACT FROM AUTHOR]

Bioinformatic data sources available on the web are multiple and heterogenous. The lack of documentation and the difficulty of interaction with these data banks require users competence in both informatics and biological fields for an optimal use of sources contents that remain rather under exploited. In this paper we present an approach based on formal concept analysis to classify and search relevant bioinformatic data sources for a given user query. It consists in building the concept lattice from the binary relation between bioinformatic data sources and their associated metadata. The concept built from a given user query is then merged into the concept lattice. The result is given by the extraction of the set of sources belonging to the extents of the query concept subsumers in the resulting concept lattice. The sources ranking is given by the concept specificity order in the concept lattice. An improvement of the approach consists in automatic refinement of the query thanks to domain ontologies. Two forms of refinement are possible by generalisation and by specialisation. [ABSTRACT FROM AUTHOR]

A machine learning technique for handling scenarios of interaction between conflicting agents is suggested. Scenarios are represented by directed graphs with labeled vertices (for mental actions) and arcs (for temporal and causal relationships between these actions and their parameters). The relation between mental actions and their descriptions gives rise to a concept lattice. Classification of an undetermined scenario is realized by comparing partial matchings of its graph with graphs of positive and negative examples. Developed scenario representation and comparative analysis techniques are applied to the classification of textual customer complaints. [ABSTRACT FROM AUTHOR]

This paper introduces D-SIFT, a Web-based browser application that provides untrained users in Formal Concept Analysis with practical and intuitive access to core analysis functionality in Formal Concept Analysis. D-SIFT is an information systems architecture that supports natural search processes over a predefined database schema and its attribute values. This enables the user to build concept lattices interactively through the selection and refinement of dynamic definitions of search boundaries (via interaction with an object "zoom" feature), and dynamic selection of search scales (via interaction with an attribute "filter" feature), based on the attribute values contained within the database. The paper investigates the claim that D-SIFT systems are an advance on the search and analysis paradigm of the Toscana-system workflow. In detail, the paper presents the architecture of the D-SIFT browser and illustrates the resulting D-SIFT-systems on an example database. The two examples illustrate the generality of system integration outcomes from D-SIFT. The Conceptual Information Systems that result from applying the D-SIFT architecture present a new workflow for building and interacting with Formal Concept Analysis-based information systems. The workflow more closely aligns with dynamic schema interaction, a popular technique used in conceptual modeling. [ABSTRACT FROM AUTHOR]

Concept lattices assist human understanding in three ways: firstly, by collecting formal concepts that contain maximal sets of objects with shared attributes; secondly, the relatedness of concepts is revealed by providing a hierarchy of formal concepts in the information space. Finally, the concept lattice (drawn as a line diagram) reveals inferences that can automatically derive association rules. Therefore, a major hypothesis of the application of concept lattices is that they visually assist in understanding the structure of information contained within an information space. However, there has been little in the way of empirical tests to substantiate this hypothesis. This paper describes the process and results of a usability evaluation for a program called Mail-Strainer, a Web-based variant of the Mail-Sleuth program, which in turn is based on the Conceptual Email Manager (Cem). [ABSTRACT FROM AUTHOR]

We describe the ‘Hierarchical as View' approach to knowledge integration from heterogeneous sources. This is based on a novel representation called Layered Conceptual Graphs (LCGs), a hierarchical extension of conceptual graphs that address interoperability issues. We introduce LCGs on the basis of a new graph transformation system, which could be an appropriate hierarchical graph model for applications that require consistent transformations. We highlight a new type of rendering based on the additional expansion of relation nodes. Both the querying and integration capabilities of our approach are based on projection, an operation also defined for simple conceptual graphs. Integration is performed in a way that neither depends on the order in which the sources are combined nor on their physical availability. [ABSTRACT FROM AUTHOR]

Our classical understanding of objects in spatiotemporal systems is based on the idea that such an object is at each moment at exactly one place. As long as the notions of "moment" and "place" are not made explicit in their granularity the meaning of that idea is not clear. It became clear by the introduction of Conceptual Time Systems with Actual Objects and a Time Relation (CTSOT) using an explicit granularity description for space and time and an object representation such that each object is at each moment in exactly one state - where the states are formal concepts of the CTSOT. For the purpose of introducing also a granularity tool for the objects the author has defined Conceptual Semantic Systems where relational information is combined with the granularity tool of conceptual scales. That led to a mathematical definition of particles and waves such that the usual notions of particles and waves in physics are covered. Waves and wave packets are "distributed objects" in the sense that they may appear simultaneously at several places. Now the question arises how to introduce a mathematical notion for the "state of a distributed object", as for example the state of an electron or the state of an institution, in the general framework of Conceptual Semantic Systems. That question is answered in this paper by the introduction of the notion of the "aspect of a concept $\textbf{c}$ with respect to some view Q", in short "the Q-aspect of $\textbf{c}$" which is defined as a suitable set of formal concepts. For spatiotemporal Conceptual Semantic Systems the state of an object $\textbf{p}$ at a time granule $\textbf{t}$ is defined as the spatial aspect of the infimum of "realizations" of $\textbf{p}$ and $\textbf{t}$. The one-element states of "actual objects" in a CTSOT are special cases of these states which may have many elements. The information units (instances) of a Conceptual Semantic System connect the concepts of different semantical scales, for example scales for objects, space, and time. That allows for defining the information distribution of the Q-aspect of a distributed object $\textbf{c}$ which leads to a mathematical definition of the "BORN-frequency"; that is defined as a relative frequency of information units which can be understood as a very meaningful mathematical representation of the famous "probability distribution of a quantum mechanical system". [ABSTRACT FROM AUTHOR]

This paper is concerned with incorporating negational relationships into the semantics of Contextual Logic by mathematizing Aristotle's Syllogistic in contextual-logic terms. For preparing this, a short sketch of Aristotle's Syllogistic is presented. Then it is shown how a contextual semantics for Aristotle's syllogisms can be developed on the basis of so-called syllogistic contexts. This semantic approach is used to determine implication bases for elementary judgments within syllogistic contexts. Finally, directions of further research are mentioned. [ABSTRACT FROM AUTHOR]