# Conceptual graph > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Conceptual_graph > Markdown URL: https://mediated.wiki/source/Conceptual_graph.md > Source: https://en.wikipedia.org/wiki/Conceptual_graph > Source revision: 1234241798 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Formalism for knowledge representation}} {{InfoMaps}} A '''conceptual graph''' ('''CG''') is a formalism for [knowledge representation](/source/knowledge_representation). In the first published paper on CGs, [John F. Sowa](/source/John_F._Sowa) used them to represent the [conceptual schema](/source/conceptual_schema)s used in [database system](/source/database_system)s.{{sfn|Sowa|1976}} The first book on CGs applied them to a wide range of topics in [artificial intelligence](/source/artificial_intelligence), [computer science](/source/computer_science), and [cognitive science](/source/cognitive_science).{{sfn|Sowa|1984}} == Research branches == Since 1984, the model has been developed along three main directions: a graphical interface for [first-order logic](/source/first-order_logic), a [diagrammatic](/source/Diagram) calculus of logics, and a [graph](/source/graph_(discrete_mathematics))-based [knowledge representation and reasoning](/source/knowledge_representation_and_reasoning) model.{{sfn|Sowa|1984}} === Graphical interface for first-order logic === thumb|left|250px|Elsie the cat is sitting on a mat In this approach, a formula in [first-order logic](/source/first-order_logic) (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](/source/ISO_standard) for [common logic](/source/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: {{code|[Cat Elsie] [Sitting *x] [Mat *y] (agent ?x Elsie) (location ?x ?y)}} 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: {{code|(exists ((x Sitting) (y Mat)) (and (Cat Elsie) (agent x Elsie) (location x y)))}} As this example shows, the asterisks on the coreference labels {{code|*x}} and {{code|*y}} in CGIF map to existentially quantified variables in CLIF, and the question marks on {{code|?x}} and {{code|?y}} map to bound variables in CLIF. A universal quantifier, represented {{code|@every*z}} in CGIF, would be represented {{code|forall (z)}} in CLIF. Reasoning can be done by translating graphs into logical formulas, then applying a logical [inference engine](/source/inference_engine). === Diagrammatic calculus of logics === Another research branch continues the work on [existential graph](/source/existential_graph)s of [Charles Sanders Peirce](/source/Charles_Sanders_Peirce), which were one of the origins of conceptual graphs as proposed by Sowa. In this approach, developed in particular by Dau {{harv|Dau|2003}}, conceptual graphs are conceptual [diagram](/source/diagram)s rather than graphs in the sense of [graph theory](/source/graph_theory), 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:{{sfn|Chein|Mugnier|2009}} * 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](/source/graph_homomorphism); this allows, in particular, to link basic reasoning problems to other fundamental problems in computer science (e.g., problems concerning [conjunctive queries](/source/Conjunctive_query) in [relational database](/source/relational_database)s, or [constraint satisfaction problems](/source/constraint_satisfaction_problem)). * The formalism is logically founded, i.e., it has a semantics in [first-order logic](/source/first-order_logic) 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++](/source/C%2B%2B) 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](/source/RDF_Schema) and conversely). ==See also== * [Alphabet of human thought](/source/Alphabet_of_human_thought) * [Chunking (psychology)](/source/Chunking_(psychology)) * [Resource Description Framework](/source/Resource_Description_Framework) (RDF) * [SPARQL](/source/SPARQL) (Graph Query Language) * [Semantic network](/source/Semantic_network) ==References== {{reflist}} ===Bibliography=== * {{cite book |last1=Chein |first1=Michel |last2=Mugnier |first2=Marie-Laure |year=2009 |title=Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs |publisher=Springer |url=http://www.lirmm.fr/gbkrbook/ |isbn=978-1-84800-285-2 | doi=10.1007/978-1-84800-286-9}} * {{cite book |last=Dau |first=F. |year=2003 |title=The Logic System of Concept Graphs with Negation and Its Relationship to Predicate Logic |series=[Lecture Notes in Computer Science](/source/Lecture_Notes_in_Computer_Science) |volume=2892 |publisher=Springer }} * {{cite journal |last=Sowa |authorlink = John Sowa |first=John F. |date=July 1976 |title=Conceptual Graphs for a Data Base Interface |journal=IBM Journal of Research and Development |volume=20 |issue=4 |pages=336–357 |url=http://www.research.ibm.com/journal/rd/204/ibmrd2004E.pdf |doi=10.1147/rd.204.0336}} * {{cite book |last=Sowa |first=John F. |year=1984 |title=Conceptual Structures: Information Processing in Mind and Machine |url=https://archive.org/details/conceptualstruct0000sowa |url-access=registration |location=Reading, MA |publisher=Addison-Wesley |isbn=978-0-201-14472-7 }} * {{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== * [http://conceptualgraphs.org Conceptual Graphs Home Page] * [https://dblp.org/streams/conf/iccs Annual international conferences (ICCS)] at [DBLP](/source/DBLP) * [http://www.jfsowa.com/cg/index.htm Conceptual Graphs on John F. Sowa's Website] Category:Knowledge representation Category:Diagrams Category:Application-specific graphs --- Adapted from the Wikipedia article [Conceptual graph](https://en.wikipedia.org/wiki/Conceptual_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Conceptual_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.