Skip to main content

2009 | Buch

Conceptual Structures: Leveraging Semantic Technologies

17th International Conference on Conceptual Structures, ICCS 2009, Moscow, Russia, July 26-31, 2009. Proceedings

herausgegeben von: Sebastian Rudolph, Frithjof Dau, Sergei O. Kuznetsov

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Inhaltsverzeichnis

Frontmatter

Invited Papers

The Maturing Semantic Web: Lessons in Web-Scale Knowledge Representation
Abstract
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.
Mark Greaves
Concept Formation in Linguistic Ontologies
Abstract
Problems of conceptualization in linguistic ontologies are discussed We show that it is necessary to form concepts of a linguistic ontology as close as possible to the meanings of linguistic units, because excessive generalization and clustering of meanings necessarily lead to distortions in the system of relations, excessive problems in a specific subject field, or an application. At the same time it is important to ensure that concepts can be distinguished from superconcepts and sibling concepts. The usage of really existing multiword expressions helps us mitigate these contradictory requirements. The introduction of concepts on the basis of multiword expressions does not change the essence of a linguistic ontology, but also makes the distinction between the concepts much clearer.
Natalia Loukachevitch
Conceptual Graph Rules and Equivalent Rules: A Synthesis
Abstract
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.
Marie-Laure Mugnier
Two Paradigms Are Better Than One, and Multiple Paradigms Are Even Better
Abstract
During the past half century, the field of artificial intelligence has developed a large number of theories, paradigms, technologies, and tools. Many AI systems are based on one dominant paradigm with a few subsidiary modules for handling exceptions or special cases. Some systems are built from components that perform different tasks, but each component is based on a single paradigm. Since people freely switch from one method of thinking or reasoning to another, some cognitive scientists believe that the ability to integrate multiple methods of reasoning is key to human-like flexibility. In his book The Society of Mind, Minsky (1986) presented an architecture for intelligence based on a society of heterogeneous agents that use different reasoning methods to solve different problems or different aspects of the same problem. That idea is intriguing, but it raises many serious issues:  how to coordinate multiple agents, distribute tasks among them, evaluate their results, encourage agents that consistently produce good results, inhibit agents that produce misleading, irrelevant, or unfruitful results, and integrate all the results into a coherent response. The most difficult problem is to enable multiple heterogeneous agents, acting independently, to produce the effect of a single mind with a unified personality that can pursue and accomplish coherent goals. This article discusses ways of organizing a society of heterogeneous agents as an integrated system with flexible methods of reasoning, learning, and language processing.
Arun K. Majumdar, John F. Sowa
Semantic Search – Using Graph-Structured Semantic Models for Supporting the Search Process
Abstract
Semantic search attempts to go beyond the current state of the art in information access by addressing information needs on the semantic level, i.e. considering the meaning of users’ queries and the available resources. In recent years, there have been significant advances in developing and applying semantic technologies to the problem of semantic search. To collate these various approaches and to try to better understand what the concept of semantic search entails, we describe semantic search from a process perspective. We argue that semantics can be exploited in all steps of this process. We describe the elements involved in the process using graph-structured, semantic models and present our existing work on semantic search in terms of this process.
Thanh Tran, Peter Haase, Rudi Studer
Human Being and Mathematics Logical and Mathematical Thinking
Summary
Logical thinking as an expression of human reason grasps the actual reality by the basic forms of thinking: concept, judgment, and conclusion. Mathematical thinking abstracts from logical thinking to disclose a cosmos of forms of potential realities hypothetically. Mathematics as a form of mathematical thinking can therefore support humans within their logical thinking about realities which, in particular, promotes sensible actions. This train of thought has been convincingly differentiated by Peirce’s philosophical pragmatism and concretized by a “contextual logic” invented by members of the mathematics department at the TU Darmstadt.
Rudolf Wille

Accepted Papers

Default Conceptual Graph Rules: Preliminary Results for an Agronomy Application
Abstract
In this paper, we extend Simple Conceptual Graphs with Reiter’s default rules. The motivation for this extension came from the type of reasonings involved in an agronomy application, namely the simulation of food processing. Our contribution is many fold: first, the expressivity of this new language corresponds to our modeling purposes. Second, we provide an effective characterization of sound and complete reasonings in this language. Third, we identify a decidable subclass of Reiter’s default logics. Last we identify our language as a superset of \(\mathcal{SREC}^-\), and provide the lacking semantics for the latter language.
Jean-François Baget, Madalina Croitoru, Jérôme Fortin, Rallou Thomopoulos
Towards Extraction of Conceptual Structures from Electronic Health Records
Abstract
This paper presents the general framework and the current results of a project that aims to develop a system for knowledge discovery and extraction from the texts of Electronic Health Records in Bulgarian language. The proposed hybrid approach integrates language technologies and conceptual processing. The system generates conceptual graphs encoding the patient case history, which contains templates for the patient’s diseases, symptoms and treatments. We describe simple inference in the generated graphs resource bank. Some experiments and their evaluation are presented in the article.
Svetla Boytcheva, Galia Angelova
Algorithm Design Using Traversals of the Covering Relation
Abstract
Where posets are used to represent taxonomies, concept lattices, or information ordered databases there is a need to engineer algorithms that search, update, and transform posets. This paper demonstrates an approach to designing such algorithms. It presents a picture of covering relation traversals that characterises these in terms of up-set and down-set expressions involving union, intersection, and difference. It then provides a detailed analysis of three types of covering relation traversal. The approach is demonstrated by describing a suite of derived algorithms. The intention is to express a manner of decomposing mathematical problems into poset traversals, and to provide context to the selection a particular traversal algorithm. This line of work has previously been pursued by [1]. However, the success and influence of Formal Concept Analysis [2] has shifted the emphasis from posets to lattices, and from algorithms that operate on the graph of the partial order to the formal context. This paper contributes a methodology for the renewed investigation of poset algorithms, with the potential to lead to improvements in algorithms such as the online completion to a lattice.
Andrew Burrow
Representing and Reasoning about Different Viewpoints: An Agronomy Application
Abstract
Real-world applications are often complex systems where several ways of analysing a given situation can be expressed, depending on actors’ viewpoints. This paper proposes a semantically sound syntactic extension to Conceptual Graphs, namely Conceptual Graph Assemblies (CGAs), that allows the representation of multiple viewpoints on the same situation. Several reasoning mechanisms, based on the projection operation, corresponding to different strength levels and adapted to multi-viewpoints situations are then demonstrated. Several modelling scenarios are then proposed and our work is put in the context of real world examples from the agri-food domain.
Madalina Croitoru, Rallou Thomopoulos
Access Policy Design Supported by FCA Methods
Abstract
Role Based Access Control (RBAC) is a methodology for providing users in an IT system specific permissions like write or read to users. It abstracts from specific users and binds permissions to user roles. Similarly, one can abstract from specific documents and bind permission to document types.
In this paper, we apply Description Logics (DLs) to formalize RBAC. We provide a thorough discussion on different possible interpretations of RBAC matrices and how DLs can be used to capture the RBAC constraints. We show moreover that with DLs, we can express more intended constraints than it can be done in the common RBAC approach, thus proving the benefit of using DLs in the RBAC setting. For deriving additional constraints, we introduce a strict methodology, based on attribute exploration method known from Formal Concept Analysis. The attribute exploration allows to systematically finding unintended implications and to deriving constraints and making them explicit. Finally, we apply our approach to a real-life example.
Frithjof Dau, Martin Knechtel
Using VRML Technology for Visualization of Relations between the Main Concepts of an Educational Course
Abstract
This paper proposes to use the VRML technology to save and display visual schemes of Topic Maps representing the structures of educational subjects. As learning purposes always require the careful selection of the most pertinent concepts from the total scientific knowledge, the rendering of Topic Maps for educational scope need not be too large. Special software has been developed to convert the original TM files into corresponding VRML 3D scenes. Processing of several computer science courses has already produced satisfactory images, and work to improve the visualization will continue.
Evgeny Eremin
Efficient Browsing and Update of Complex Data Based on the Decomposition of Contexts
Abstract
Formal concept analysis is recognized as a good paradigm for browsing data sets. Besides browsing, update and complex data are other important aspects of information systems. To have an efficient implementation of concept-based information systems is difficult because of the diversity of complex data and the computation of conceptual structures, but essential for the scalability to real-world applications. We propose to decompose contexts into simpler and specialized components: logical context functors. We demonstrate this allows for scalable implementations, updatable ontologies, and richer navigation structures, while retaining genericity.
Sébastien Ferré
In Search of Semantic Compositionality in Vector Spaces
Abstract
In spite of the widespread usage of geometric models of meaning in computational linguistics and information retrieval research, they have been until recently mostly utilized for modeling lexical meaning. The ability to deal with concept combination, however, is the essential capacity of human language, and any semantic theory should be able to handle it.
Making use of Word Space Models (Schütze 1998) and Random Indexing (Sahlgren 2005), we explore the hypothesis that compositional meaning can be captured in such models by adopting a number of mathematical operations for vector composition (summation, component product, tensor product and convolution) to model semantic composition in a multiword unit identification task.
Eugenie Giesbrecht
Frequent Itemset Mining for Clustering Near Duplicate Web Documents
Abstract
A vast amount of documents in the Web have duplicates, which is a challenge for developing efficient methods that would compute clusters of similar documents. In this paper we use an approach based on computing (closed) sets of attributes having large support (large extent) as clusters of similar documents. The method is tested in a series of computer experiments on large public collections of web documents and compared to other established methods and software, such as biclustering, on same datasets. Practical efficiency of different algorithms for computing frequent closed sets of attributes is compared.
Dmitry I. Ignatov, Sergei O. Kuznetsov
System Consequence
Abstract
This paper discusses system consequence, a central idea in the project to lift the theory of information flow to the abstract level of universal logic and the theory of institutions. The theory of information flow is a theory of distributed logic. The theory of institutions is abstract model theory. A system is a collection of interconnected parts, where the whole may have properties that cannot be known from an analysis of the constituent parts in isolation. In an information system, the parts represent information resources and the interconnections represent constraints between the parts. System consequence, which is the extension of the consequence operator from theories to systems, models the available regularities represented by an information system as a whole. System consequence (without part-to-part constraints) is defined for a specific logical system (institution) in the theory of information flow. This paper generalizes the idea of system consequence to arbitrary logical systems.
Robert E. Kent
Fusion of Claude Bernard’s Experiments for Scientific Discovery Reasoning
Abstract
We are interested in using a fusion process to complete information prior to the reasoning process about scientific discoveries. In particular, using fusion to complete the set of experiments used as the source of information of the process that led Claude Bernard to his discovery about the effects of curare. Our reconstruction of the discovery process is based on his experiments as they are illustrated in his notebooks. Our main problem is the lack of some important information in his notebooks containing descriptions of his set of experiments. In order to fill in the gaps in his set of experiments, we propose to use fusion between experiments. Prior to fusion, we must ensure that the experiments are compatible according to some similarity measures and depending on the objectives of the fusion. The paper presents our domain-independent approach for similarity checking and fusion, including similarity and fusion strategies.
Claire Laudy, Bassel Habib, Jean-Gabriel Ganascia
Distinguishing Answers in Conceptual Graph Knowledge Bases
Abstract
In knowledge bases (KB), the open world assumption and the ability to express variables may lead to an answer redundancy problem. This problem occurs when the returned answers are comparable. In this paper, we define a framework to distinguish amongst answers. Our method is based on adding contextual knowledge extracted from the KB. The construction of such descriptions allows clarification of the notion of redundancy between answers, based not only on the images of the requested pattern but also on the whole KB. We propose a definition for the set of answers to be computed from a query, which ensures both properties of non-redundancy and completeness. While all answers of this set can be distinguished from others with a description, an open question remains concerning what is a good description to return to an end-user. We introduce the notion of smart answer and give an algorithm that computes a set of smart answers based on a vertex neighborhood distance.
Nicolas Moreau, Michel Leclère, Madalina Croitoru
A Practical Exploration of Ontology Interoperability
Abstract
ISO Common Logic (CL, ISO/IEC 24707:2007) offers the Semantic Web (SW) a new and powerful dimension in achieving the effective discovery, automation, integration, and reuse across applications, data and knowledge. The paper shows how it is possible to explore such interoperability through small scale exemplar projects. As Conceptual Graphs (CG) is a key technology in CL, we focused on the Amine CG software and for the SW we focused on the Protégé OWL software, exploring the possible mappings between ontologies captured in OWL and in Amine. Through this practical exercise the dimensions and extent of the desired interoperability could be demonstrated. This small but significant experiment provided a practical insight into how CG Tools can actually interoperate towards achieving the wider goal of Ontology interoperability between CL and the SW.
Simon Polovina, James Cooke, Jeremy Loke
Relation Algebra Operations on Formal Contexts
Abstract
This paper discusses the use of relation algebra operations on formal contexts. These operations are a generalisation of some of the context operations that are described in the standard FCA textbook (Ganter & Wille, 1999). This paper extends previous research in this area with respect to applications and implementations. It also describes a software tool (FcaFlint) which in combination with FcaStone facilitates the application of relation algebra operations to contexts stored in many formats.
Uta Priss
Conceptual Graphs and Datatypes
Abstract
Datatypes, like numbers or strings, are widely used in Knowledge Representation (e.g. in RDF(S)/OWL or UML languages). The usual model of simple conceptual graphs does not support datatypes. Some extensions of conceptual graphs have been proposed for using datatypes, however these extensions often wander from initial model of conceptual graphs by introducing for instance procedural relations between nodes. This paper proposes a datatype extension for the simple conceptual graph model. Our contribution is threefold. First, we allow the use of datatypes for typing concept nodes. Second, we define two families of conceptual graphs: factual graphs and query graphs, both close to initial model. Factual graph is used to represent factual knowledge, including values of datatypes. Query graph may contain concept nodes that represent conditional queries on values of datatypes; these conditions are expressed by regular operators on datatypes. Third, we adapt projection to operate from a query graph to a factual graph.
Thomas Raimbault, David Genest, Stéphane Loiseau
Towards the Complexity of Recognizing Pseudo-intents
Abstract
Pseudo-intents play a key rôle in Formal Concept Analysis. They are the premises of the implications in the Duquenne-Guigues Base, which is a minimum cardinality base for the set of implications that hold in a formal context. It has been shown that checking whether a set is a pseudo-intent is in conp. However, it is still open whether this problem is conp-hard, or it is solvable in polynomial time. In the current work we prove a first lower bound for this problem by showing that it is at least as hard as transversal hypergraph, which is the problem of identifying the minimal transversals of a given hypergraph. This is a prominent open problem in hypergraph theory that is conjectured to form a complexity class properly contained between p and conp. Our result explains why the attempts to find a polynomial algorithm for recognizing pseudo-intents have failed until now. We also formulate a decision problem, namely first pseudo-intent, and show that if this problem is not polynomial, then, unless p = np, pseudo-intents cannot be enumerated with polynomial delay in a specified lexicographic order.
Barış Sertkaya
Another Reason Why Conceptual Graphs Need Actors
Abstract
Conceptual graphs (CGs) are a knowledge representation formalism that models monotonic first-order logic. However, in the case of an active knowledge base and in other cases, it is necessary to modify a CG dynamically, rendering the preceding static first-order CG possibly inconsistent and in need of further analysis. In order to extend monotonic first-order logic to non-monotonic second-order computation, and therefore achieve all of the power of a modern computer, CGs need to use atomic actors to represent change. To illustrate the power of actors, we represent the well-defined Turing machine; this has the added effect of showing that CGs can represent any of the power of a modern computer. This addition to the CG theory will have other similar practical effects.
B. J. Smith, Harry Delugach
Relational Scaling in Relational Semantic Systems
Abstract
In this paper two developments in Conceptual Knowledge Processing are combined, namely Contextual Logic introduced by Rudolf Wille and Temporal Concept Analysis introduced by the author. The basic structures connecting both theories are Relational Semantic Systems (RSS), each consisting of conceptual scales and a Relational Data Systems (RDS) for the representation of relational knowledge. We introduce the notion of a concept graph of a RSS. As opposed to the definition of a concept graph of a power context family the concepts used in the concept graph of a RSS are taken from the conceptual scales and not from the concept lattices of the contexts of k-ary relations. For the graphical representation of relational knowledge in information maps we modify tools from Temporal Concept Analysis and develop relational trace diagrams. Its usefulness is shown in a small example of a Relational Semantic System.
Karl Erich Wolff
Backmatter
Metadaten
Titel
Conceptual Structures: Leveraging Semantic Technologies
herausgegeben von
Sebastian Rudolph
Frithjof Dau
Sergei O. Kuznetsov
Copyright-Jahr
2009
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-03079-6
Print ISBN
978-3-642-03078-9
DOI
https://doi.org/10.1007/978-3-642-03079-6

Premium Partner