HOME

TheInfoList



OR:

A conceptual graph (CG) is a formalism for
knowledge representation Knowledge representation and reasoning (KRR, KR&R, KR²) is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medic ...
. In the first published paper on CGs, John F. Sowa used them to represent the conceptual schemas used in database systems. The first book on CGs applied them to a wide range of topics in
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machine A machine is a physical system using Power (physics), power to apply Force, forces and control Motion, moveme ...
,
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, and cognitive science.


Research branches

Since 1984, the model has been developed along three main directions: a graphical interface for first-order logic, a diagrammatic calculus of logics, and a graph-based
knowledge representation and reasoning Knowledge representation and reasoning (KRR, KR&R, KR²) is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medic ...
model.


Graphical interface for first-order logic

In this approach, a formula in
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
(predicate calculus) is represented by a labeled graph. A linear notation, called the Conceptual Graph Interchange Format (CGIF), has been standardized in the ISO standard for common logic. The diagram above is an example of the ''display form'' for a conceptual graph. Each box is called a ''concept node'', and each oval is called a ''relation node''. In CGIF, this CG would be represented by the following statement: In CGIF, brackets enclose the information inside the concept nodes, and parentheses enclose the information inside the relation nodes. The letters x and y, which are called ''coreference labels'', show how the concept and relation nodes are connected. In CLIF, those letters are mapped to variables, as in the following statement: As this example shows, the asterisks on the coreference labels and in CGIF map to existentially quantified variables in CLIF, and the question marks on and map to bound variables in CLIF. A universal quantifier, represented in CGIF, would be represented in CLIF. Reasoning can be done by translating graphs into logical formulas, then applying a logical inference engine.


Diagrammatic calculus of logics

Another research branch continues the work on existential graphs of
Charles Sanders Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for ...
, which were one of the origins of conceptual graphs as proposed by Sowa. In this approach, developed in particular by Dau , conceptual graphs are conceptual diagrams rather than graphs in the sense of
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, and reasoning operations are performed by operations on these diagrams.


Graph-based knowledge representation and reasoning model

Key features of GBKR, the graph-based knowledge representation and reasoning model developed by Chein and Mugnier and the Montpellier group , can be summarized as follows: * All kinds of knowledge (ontology, rules, constraints and facts) are labeled graphs, which provide an intuitive and easily understandable means to represent knowledge. * Reasoning mechanisms are based on graph notions, basically the classical notion of graph homomorphism; this allows, in particular, to link basic reasoning problems to other fundamental problems in computer science (e.g., problems concerning conjunctive queries in relational databases, or constraint satisfaction problems). * The formalism is logically founded, i.e., it has a semantics in
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
and the inference mechanisms are sound and complete with respect to deduction in first-order logic. * From a computational viewpoint, the graph homomorphism notion was recognized in the 1990s as a central notion, and complexity results and efficient algorithms have been obtained in several domains. COGITANT and COGUI are tools that implement the GBKR model. COGITANT is a library of C++ classes that implement most of the GBKR notions and reasoning mechanisms. COGUI is a graphical user interface dedicated to the construction of a GBKR knowledge base (it integrates COGITANT and, among numerous functionalities, it contains a translator from GBKR to RDF/S and conversely).


See also

* Alphabet of human thought * Chunking (psychology) * Resource Description Framework (RDF) * SPARQL (Graph Query Language) * Semantic network


References

* * * * * {{cite journal, title=Conceptual graphs for the analysis and generation of sentences , first1=Paola , last1=Velardi , first2=Maria Teresa , last2=Pazienza , first3=Mario , last3=De' Giovanetti , journal=IBM Journal of Research and Development , volume=32 , number=2 , date=March 1988 , pages=251–267 , publisher=IBM Corp. Riverton, NJ, USA , doi=10.1147/rd.322.0251


External links


Conceptual Structures Home Page
(Old site
Conceptual Graphs Home Page

Annual international conferences (ICCS)
at
DBLP DBLP is a computer science bibliography website. Starting in 1993 at Universität Trier in Germany, it grew from a small collection of HTML files and became an organization hosting a database and logic programming bibliography site. Since No ...

Conceptual Graphs on John F. Sowa's Website
Knowledge representation Diagrams Application-specific graphs