Document (#23080)

Author

Mugnier, M.-L.

Title

Knowledge representation and reasonings based on graph homomorphisms

Source

Conceptual structures: logical, linguistic, and computational issues. 8th International Conference on Conceptual Structures, ICCS 2000, Darmstadt, Germany, August 14-18, 2000. Ed.: B. Ganter et al

Imprint

Berlin : Springer

Year

2000

Pages

S.172-192

Series

Lecture notes in computer science; vol.1867: Lecture notes on artificial intelligence

Abstract

The main conceptual contribution in this paper is to present an approach to knowledge representation and reasonings based on labeled graphs and labeled graph homomorphism. Strengths and weaknesses of this graph-based approach are discussed. Main technical contributions are the followings. Fundamental results about the kernel of this approach, the so-called simple graphs model are synthesized. It is then shown that the basic deduction problem on simple graphs is essentially the same problem as conjunctive query containment in databases and constraint satisfaction; polynomial parcimonious transformations between these problems are exhibited. Grounded on the simple graphs model, a knowledge representation and reasoning model allowing to deal with facts, production rules, transformation rules, and constraints is presented, as an illustration of the graph-based approach.

Similar documents (content)

1. Song, N.; Cheng, H.; Zhou, H.; Wang, X.: Linking scholarly contents : the design and construction of an argumentation graph (2022) 0.29

   0.28715777 = sum of:
     0.28715777 = product of:
       1.0255635 = sum of:
         0.008066116 = weight(abstract_txt:this in 1104) [ClassicSimilarity], result of:
           0.008066116 = score(doc=1104,freq=1.0), product of:
             0.04278721 = queryWeight, product of:
               1.0681943 = boost
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.016599815 = queryNorm
             0.18851699 = fieldWeight in 1104, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.078125 = fieldNorm(doc=1104)
         0.0514898 = weight(abstract_txt:knowledge in 1104) [ClassicSimilarity], result of:
           0.0514898 = score(doc=1104,freq=4.0), product of:
             0.09275382 = queryWeight, product of:
               1.5727481 = boost
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.016599815 = queryNorm
             0.5551232 = fieldWeight in 1104, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.078125 = fieldNorm(doc=1104)
         0.036363978 = weight(abstract_txt:model in 1104) [ClassicSimilarity], result of:
           0.036363978 = score(doc=1104,freq=1.0), product of:
             0.11676659 = queryWeight, product of:
               1.7646255 = boost
               3.986234 = idf(docFreq=2231, maxDocs=44218)
               0.016599815 = queryNorm
             0.31142452 = fieldWeight in 1104, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.986234 = idf(docFreq=2231, maxDocs=44218)
               0.078125 = fieldNorm(doc=1104)
         0.024799744 = weight(abstract_txt:based in 1104) [ClassicSimilarity], result of:
           0.024799744 = score(doc=1104,freq=1.0), product of:
             0.09957463 = queryWeight, product of:
               1.8816419 = boost
               3.1879277 = idf(docFreq=4958, maxDocs=44218)
               0.016599815 = queryNorm
             0.24905685 = fieldWeight in 1104, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1879277 = idf(docFreq=4958, maxDocs=44218)
               0.078125 = fieldNorm(doc=1104)
         0.097052604 = weight(abstract_txt:representation in 1104) [ClassicSimilarity], result of:
           0.097052604 = score(doc=1104,freq=2.0), product of:
             0.17831962 = queryWeight, product of:
               2.1806843 = boost
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.016599815 = queryNorm
             0.54426205 = fieldWeight in 1104, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.078125 = fieldNorm(doc=1104)
         0.532443 = weight(abstract_txt:graph in 1104) [ClassicSimilarity], result of:
           0.532443 = score(doc=1104,freq=6.0), product of:
             0.42330056 = queryWeight, product of:
               3.879601 = boost
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.016599815 = queryNorm
             1.2578367 = fieldWeight in 1104, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.078125 = fieldNorm(doc=1104)
         0.27534828 = weight(abstract_txt:graphs in 1104) [ClassicSimilarity], result of:
           0.27534828 = score(doc=1104,freq=1.0), product of:
             0.4955705 = queryWeight, product of:
               4.197738 = boost
               7.11192 = idf(docFreq=97, maxDocs=44218)
               0.016599815 = queryNorm
             0.55561876 = fieldWeight in 1104, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.11192 = idf(docFreq=97, maxDocs=44218)
               0.078125 = fieldNorm(doc=1104)
       0.28 = coord(7/25)
   

2. Auer, S.; Oelen, A.; Haris, A.M.; Stocker, M.; D'Souza, J.; Farfar, K.E.; Vogt, L.; Prinz, M.; Wiens, V.; Jaradeh, M.Y.: Improving access to scientific literature with knowledge graphs : an experiment using library guidelines to judge information integrity (2020) 0.22

   0.22466964 = sum of:
     0.22466964 = product of:
       0.8023915 = sum of:
         0.009125768 = weight(abstract_txt:this in 316) [ClassicSimilarity], result of:
           0.009125768 = score(doc=316,freq=2.0), product of:
             0.04278721 = queryWeight, product of:
               1.0681943 = boost
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.016599815 = queryNorm
             0.21328263 = fieldWeight in 316, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.0625 = fieldNorm(doc=316)
         0.054491684 = weight(abstract_txt:knowledge in 316) [ClassicSimilarity], result of:
           0.054491684 = score(doc=316,freq=7.0), product of:
             0.09275382 = queryWeight, product of:
               1.5727481 = boost
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.016599815 = queryNorm
             0.5874872 = fieldWeight in 316, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.0625 = fieldNorm(doc=316)
         0.019839795 = weight(abstract_txt:based in 316) [ClassicSimilarity], result of:
           0.019839795 = score(doc=316,freq=1.0), product of:
             0.09957463 = queryWeight, product of:
               1.8816419 = boost
               3.1879277 = idf(docFreq=4958, maxDocs=44218)
               0.016599815 = queryNorm
             0.19924548 = fieldWeight in 316, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1879277 = idf(docFreq=4958, maxDocs=44218)
               0.0625 = fieldNorm(doc=316)
         0.07764208 = weight(abstract_txt:representation in 316) [ClassicSimilarity], result of:
           0.07764208 = score(doc=316,freq=2.0), product of:
             0.17831962 = queryWeight, product of:
               2.1806843 = boost
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.016599815 = queryNorm
             0.43540964 = fieldWeight in 316, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.0625 = fieldNorm(doc=316)
         0.032172244 = weight(abstract_txt:approach in 316) [ClassicSimilarity], result of:
           0.032172244 = score(doc=316,freq=1.0), product of:
             0.13743947 = queryWeight, product of:
               2.2106416 = boost
               3.745328 = idf(docFreq=2839, maxDocs=44218)
               0.016599815 = queryNorm
             0.234083 = fieldWeight in 316, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.745328 = idf(docFreq=2839, maxDocs=44218)
               0.0625 = fieldNorm(doc=316)
         0.38884133 = weight(abstract_txt:graph in 316) [ClassicSimilarity], result of:
           0.38884133 = score(doc=316,freq=5.0), product of:
             0.42330056 = queryWeight, product of:
               3.879601 = boost
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.016599815 = queryNorm
             0.91859394 = fieldWeight in 316, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.0625 = fieldNorm(doc=316)
         0.2202786 = weight(abstract_txt:graphs in 316) [ClassicSimilarity], result of:
           0.2202786 = score(doc=316,freq=1.0), product of:
             0.4955705 = queryWeight, product of:
               4.197738 = boost
               7.11192 = idf(docFreq=97, maxDocs=44218)
               0.016599815 = queryNorm
             0.444495 = fieldWeight in 316, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.11192 = idf(docFreq=97, maxDocs=44218)
               0.0625 = fieldNorm(doc=316)
       0.28 = coord(7/25)
   

3. Tang, X.-B.; Fu, W.-G.; Liu, Y.: Knowledge big graph fusing ontology with property graph : a case study of financial ownership network (2021) 0.18

   0.17923589 = sum of:
     0.17923589 = product of:
       0.7468162 = sum of:
         0.011176737 = weight(abstract_txt:this in 234) [ClassicSimilarity], result of:
           0.011176737 = score(doc=234,freq=3.0), product of:
             0.04278721 = queryWeight, product of:
               1.0681943 = boost
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.016599815 = queryNorm
             0.2612168 = fieldWeight in 234, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.0625 = fieldNorm(doc=234)
         0.08261738 = weight(abstract_txt:constraint in 234) [ClassicSimilarity], result of:
           0.08261738 = score(doc=234,freq=1.0), product of:
             0.16236217 = queryWeight, product of:
               1.2013652 = boost
               8.14154 = idf(docFreq=34, maxDocs=44218)
               0.016599815 = queryNorm
             0.5088462 = fieldWeight in 234, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.14154 = idf(docFreq=34, maxDocs=44218)
               0.0625 = fieldNorm(doc=234)
         0.06513002 = weight(abstract_txt:knowledge in 234) [ClassicSimilarity], result of:
           0.06513002 = score(doc=234,freq=10.0), product of:
             0.09275382 = queryWeight, product of:
               1.5727481 = boost
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.016599815 = queryNorm
             0.7021815 = fieldWeight in 234, product of:
               3.1622777 = tf(freq=10.0), with freq of:
                 10.0 = termFreq=10.0
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.0625 = fieldNorm(doc=234)
         0.041141145 = weight(abstract_txt:model in 234) [ClassicSimilarity], result of:
           0.041141145 = score(doc=234,freq=2.0), product of:
             0.11676659 = queryWeight, product of:
               1.7646255 = boost
               3.986234 = idf(docFreq=2231, maxDocs=44218)
               0.016599815 = queryNorm
             0.35233662 = fieldWeight in 234, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.986234 = idf(docFreq=2231, maxDocs=44218)
               0.0625 = fieldNorm(doc=234)
         0.054901242 = weight(abstract_txt:representation in 234) [ClassicSimilarity], result of:
           0.054901242 = score(doc=234,freq=1.0), product of:
             0.17831962 = queryWeight, product of:
               2.1806843 = boost
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.016599815 = queryNorm
             0.30788112 = fieldWeight in 234, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.0625 = fieldNorm(doc=234)
         0.4918497 = weight(abstract_txt:graph in 234) [ClassicSimilarity], result of:
           0.4918497 = score(doc=234,freq=8.0), product of:
             0.42330056 = queryWeight, product of:
               3.879601 = boost
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.016599815 = queryNorm
             1.1619396 = fieldWeight in 234, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.0625 = fieldNorm(doc=234)
       0.24 = coord(6/25)
   

4. Yang, P.; Gao, W.; Tan, Q.; Wong, K.-F.: ¬A link-bridged topic model for cross-domain document classification (2013) 0.18

   0.17574318 = sum of:
     0.17574318 = product of:
       0.54919744 = sum of:
         0.006452893 = weight(abstract_txt:this in 2706) [ClassicSimilarity], result of:
           0.006452893 = score(doc=2706,freq=1.0), product of:
             0.04278721 = queryWeight, product of:
               1.0681943 = boost
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.016599815 = queryNorm
             0.1508136 = fieldWeight in 2706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
         0.0932897 = weight(abstract_txt:kernel in 2706) [ClassicSimilarity], result of:
           0.0932897 = score(doc=2706,freq=1.0), product of:
             0.1760596 = queryWeight, product of:
               1.251015 = boost
               8.478011 = idf(docFreq=24, maxDocs=44218)
               0.016599815 = queryNorm
             0.5298757 = fieldWeight in 2706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.478011 = idf(docFreq=24, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
         0.041191842 = weight(abstract_txt:knowledge in 2706) [ClassicSimilarity], result of:
           0.041191842 = score(doc=2706,freq=4.0), product of:
             0.09275382 = queryWeight, product of:
               1.5727481 = boost
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.016599815 = queryNorm
             0.4440986 = fieldWeight in 2706, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
         0.05038741 = weight(abstract_txt:model in 2706) [ClassicSimilarity], result of:
           0.05038741 = score(doc=2706,freq=3.0), product of:
             0.11676659 = queryWeight, product of:
               1.7646255 = boost
               3.986234 = idf(docFreq=2231, maxDocs=44218)
               0.016599815 = queryNorm
             0.4315225 = fieldWeight in 2706, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               3.986234 = idf(docFreq=2231, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
         0.019839795 = weight(abstract_txt:based in 2706) [ClassicSimilarity], result of:
           0.019839795 = score(doc=2706,freq=1.0), product of:
             0.09957463 = queryWeight, product of:
               1.8816419 = boost
               3.1879277 = idf(docFreq=4958, maxDocs=44218)
               0.016599815 = queryNorm
             0.19924548 = fieldWeight in 2706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1879277 = idf(docFreq=4958, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
         0.032172244 = weight(abstract_txt:approach in 2706) [ClassicSimilarity], result of:
           0.032172244 = score(doc=2706,freq=1.0), product of:
             0.13743947 = queryWeight, product of:
               2.2106416 = boost
               3.745328 = idf(docFreq=2839, maxDocs=44218)
               0.016599815 = queryNorm
             0.234083 = fieldWeight in 2706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.745328 = idf(docFreq=2839, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
         0.13196842 = weight(abstract_txt:labeled in 2706) [ClassicSimilarity], result of:
           0.13196842 = score(doc=2706,freq=1.0), product of:
             0.27952924 = queryWeight, product of:
               2.2292626 = boost
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.016599815 = queryNorm
             0.47210953 = fieldWeight in 2706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
         0.17389514 = weight(abstract_txt:graph in 2706) [ClassicSimilarity], result of:
           0.17389514 = score(doc=2706,freq=1.0), product of:
             0.42330056 = queryWeight, product of:
               3.879601 = boost
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.016599815 = queryNorm
             0.4108077 = fieldWeight in 2706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.0625 = fieldNorm(doc=2706)
       0.32 = coord(8/25)
   

5. Gerbé, O.; Mineau, G.W.; Keller, R.K.: Conceptual graphs, metamodelling, and notation of concepts : fundamental issues (2000) 0.17

   0.1714267 = sum of:
     0.1714267 = product of:
       0.85713345 = sum of:
         0.013688653 = weight(abstract_txt:this in 5078) [ClassicSimilarity], result of:
           0.013688653 = score(doc=5078,freq=2.0), product of:
             0.04278721 = queryWeight, product of:
               1.0681943 = boost
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.016599815 = queryNorm
             0.31992394 = fieldWeight in 5078, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4130175 = idf(docFreq=10762, maxDocs=44218)
               0.09375 = fieldNorm(doc=5078)
         0.06178776 = weight(abstract_txt:knowledge in 5078) [ClassicSimilarity], result of:
           0.06178776 = score(doc=5078,freq=4.0), product of:
             0.09275382 = queryWeight, product of:
               1.5727481 = boost
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.016599815 = queryNorm
             0.6661479 = fieldWeight in 5078, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               3.5527887 = idf(docFreq=3442, maxDocs=44218)
               0.09375 = fieldNorm(doc=5078)
         0.08235186 = weight(abstract_txt:representation in 5078) [ClassicSimilarity], result of:
           0.08235186 = score(doc=5078,freq=1.0), product of:
             0.17831962 = queryWeight, product of:
               2.1806843 = boost
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.016599815 = queryNorm
             0.46182168 = fieldWeight in 5078, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.926098 = idf(docFreq=871, maxDocs=44218)
               0.09375 = fieldNorm(doc=5078)
         0.36888728 = weight(abstract_txt:graph in 5078) [ClassicSimilarity], result of:
           0.36888728 = score(doc=5078,freq=2.0), product of:
             0.42330056 = queryWeight, product of:
               3.879601 = boost
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.016599815 = queryNorm
             0.8714547 = fieldWeight in 5078, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.572923 = idf(docFreq=167, maxDocs=44218)
               0.09375 = fieldNorm(doc=5078)
         0.33041793 = weight(abstract_txt:graphs in 5078) [ClassicSimilarity], result of:
           0.33041793 = score(doc=5078,freq=1.0), product of:
             0.4955705 = queryWeight, product of:
               4.197738 = boost
               7.11192 = idf(docFreq=97, maxDocs=44218)
               0.016599815 = queryNorm
             0.6667425 = fieldWeight in 5078, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.11192 = idf(docFreq=97, maxDocs=44218)
               0.09375 = fieldNorm(doc=5078)
       0.2 = coord(5/25)