Individual Reuse in Description Logic Reasoning View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008-01-01

AUTHORS

Boris Motik , Ian Horrocks

ABSTRACT

Tableau calculi are the state-of-the-art for reasoning in description logics (DL). Despite recent improvements, tableau-based reasoners still cannot process certain knowledge bases (KBs), mainly because they end up building very large models. To address this, we propose a tableau calculus with individual reuse: to satisfy an existential assertion, our calculus nondeterministically tries to reuse individuals from the model generated thus far. We present two expansion strategies: one is applicable to the DL \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ELOH}$\end{document} and gives us a worst-case optimal algorithm, and the other is applicable to the DL \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SHOIQ}$\end{document}. Using this technique, our reasoner can process several KBs that no other reasoner can. More... »

PAGES

242-258

Book

TITLE

Automated Reasoning

ISBN

978-3-540-71069-1
978-3-540-71070-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-71070-7_20

DOI

http://dx.doi.org/10.1007/978-3-540-71070-7_20

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1030877482


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "University of Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Motik", 
        "givenName": "Boris", 
        "id": "sg:person.07401076267.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401076267.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "University of Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Horrocks", 
        "givenName": "Ian", 
        "id": "sg:person.013100561643.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013100561643.19"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008-01-01", 
    "datePublishedReg": "2008-01-01", 
    "description": "Tableau calculi are the state-of-the-art for reasoning in description logics (DL). Despite recent improvements, tableau-based reasoners still cannot process certain knowledge bases (KBs), mainly because they end up building very large models. To address this, we propose a tableau calculus with individual reuse: to satisfy an existential assertion, our calculus nondeterministically tries to reuse individuals from the model generated thus far. We present two expansion strategies: one is applicable to the DL \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{ELOH}$\\end{document} and gives us a worst-case optimal algorithm, and the other is applicable to the DL \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{SHOIQ}$\\end{document}. Using this technique, our reasoner can process several KBs that no other reasoner can.", 
    "editor": [
      {
        "familyName": "Armando", 
        "givenName": "Alessandro", 
        "type": "Person"
      }, 
      {
        "familyName": "Baumgartner", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Dowek", 
        "givenName": "Gilles", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-71070-7_20", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-71069-1", 
        "978-3-540-71070-7"
      ], 
      "name": "Automated Reasoning", 
      "type": "Book"
    }, 
    "keywords": [
      "knowledge bases", 
      "reasoning", 
      "reasoner", 
      "individuals", 
      "description logics", 
      "logic reasoning", 
      "assertion", 
      "model", 
      "strategies", 
      "art", 
      "improvement", 
      "basis", 
      "large models", 
      "logic", 
      "state", 
      "expansion strategy", 
      "technique", 
      "recent improvements", 
      "algorithm", 
      "calculus", 
      "reuse", 
      "optimal algorithm", 
      "description logic reasoning", 
      "tableau calculus", 
      "tableau-based reasoners", 
      "worst-case optimal algorithm", 
      "existential assertions", 
      "certain knowledge bases", 
      "individual reuse"
    ], 
    "name": "Individual Reuse in Description Logic Reasoning", 
    "pagination": "242-258", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030877482"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-71070-7_20"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-71070-7_20", 
      "https://app.dimensions.ai/details/publication/pub.1030877482"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_200.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-71070-7_20"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-71070-7_20'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-71070-7_20'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-71070-7_20'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-71070-7_20'


 

This table displays all metadata directly associated to this object as RDF triples.

106 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-71070-7_20 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N438cfc054be7485790d678d1079f1670
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description Tableau calculi are the state-of-the-art for reasoning in description logics (DL). Despite recent improvements, tableau-based reasoners still cannot process certain knowledge bases (KBs), mainly because they end up building very large models. To address this, we propose a tableau calculus with individual reuse: to satisfy an existential assertion, our calculus nondeterministically tries to reuse individuals from the model generated thus far. We present two expansion strategies: one is applicable to the DL \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ELOH}$\end{document} and gives us a worst-case optimal algorithm, and the other is applicable to the DL \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SHOIQ}$\end{document}. Using this technique, our reasoner can process several KBs that no other reasoner can.
7 schema:editor N21f592fe7f374de8a6e0d765fc331224
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3ea1c92a8461460a9e35bd3b72368153
12 schema:keywords algorithm
13 art
14 assertion
15 basis
16 calculus
17 certain knowledge bases
18 description logic reasoning
19 description logics
20 existential assertions
21 expansion strategy
22 improvement
23 individual reuse
24 individuals
25 knowledge bases
26 large models
27 logic
28 logic reasoning
29 model
30 optimal algorithm
31 reasoner
32 reasoning
33 recent improvements
34 reuse
35 state
36 strategies
37 tableau calculus
38 tableau-based reasoners
39 technique
40 worst-case optimal algorithm
41 schema:name Individual Reuse in Description Logic Reasoning
42 schema:pagination 242-258
43 schema:productId N7d55c78c75954a7fb5c580aa2a5d9f5a
44 Nce803f544df94d7fa1cca18848c0d5de
45 schema:publisher N6d60d3529db64fab9ac1a0d78cb40c12
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030877482
47 https://doi.org/10.1007/978-3-540-71070-7_20
48 schema:sdDatePublished 2022-01-01T19:12
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N2c67922b41874b24a821411181287302
51 schema:url https://doi.org/10.1007/978-3-540-71070-7_20
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N21f592fe7f374de8a6e0d765fc331224 rdf:first Na374789ad0f2401e98cb60d1e333fa8d
56 rdf:rest N883686b2c4f748c899cf6c78e3b79f94
57 N2c67922b41874b24a821411181287302 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N3ea1c92a8461460a9e35bd3b72368153 schema:isbn 978-3-540-71069-1
60 978-3-540-71070-7
61 schema:name Automated Reasoning
62 rdf:type schema:Book
63 N438cfc054be7485790d678d1079f1670 rdf:first sg:person.07401076267.36
64 rdf:rest Na86299122f814e87ab24beeb628fffa9
65 N57e6fb49fd8149ddb773f6c294382fe2 schema:familyName Dowek
66 schema:givenName Gilles
67 rdf:type schema:Person
68 N6d60d3529db64fab9ac1a0d78cb40c12 schema:name Springer Nature
69 rdf:type schema:Organisation
70 N7d55c78c75954a7fb5c580aa2a5d9f5a schema:name doi
71 schema:value 10.1007/978-3-540-71070-7_20
72 rdf:type schema:PropertyValue
73 N883686b2c4f748c899cf6c78e3b79f94 rdf:first Na2dd6effdeb346368d161f66a819b4cb
74 rdf:rest Nf888f37088744e0e9642df1b334ff9f9
75 Na2dd6effdeb346368d161f66a819b4cb schema:familyName Baumgartner
76 schema:givenName Peter
77 rdf:type schema:Person
78 Na374789ad0f2401e98cb60d1e333fa8d schema:familyName Armando
79 schema:givenName Alessandro
80 rdf:type schema:Person
81 Na86299122f814e87ab24beeb628fffa9 rdf:first sg:person.013100561643.19
82 rdf:rest rdf:nil
83 Nce803f544df94d7fa1cca18848c0d5de schema:name dimensions_id
84 schema:value pub.1030877482
85 rdf:type schema:PropertyValue
86 Nf888f37088744e0e9642df1b334ff9f9 rdf:first N57e6fb49fd8149ddb773f6c294382fe2
87 rdf:rest rdf:nil
88 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
89 schema:name Psychology and Cognitive Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
92 schema:name Psychology
93 rdf:type schema:DefinedTerm
94 sg:person.013100561643.19 schema:affiliation grid-institutes:grid.4991.5
95 schema:familyName Horrocks
96 schema:givenName Ian
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013100561643.19
98 rdf:type schema:Person
99 sg:person.07401076267.36 schema:affiliation grid-institutes:grid.4991.5
100 schema:familyName Motik
101 schema:givenName Boris
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401076267.36
103 rdf:type schema:Person
104 grid-institutes:grid.4991.5 schema:alternateName University of Oxford, UK
105 schema:name University of Oxford, UK
106 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...