Extended Caching, Backjumping and Merging for Expressive Description Logics View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Andreas Steigmiller , Thorsten Liebig , Birte Glimm

ABSTRACT

With this contribution we push the boundary of some known optimisations such as caching to the very expressive Description Logic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SROIQ}$\end{document}. The developed method is based on a sophisticated dependency management and a precise unsatisfiability caching technique, which further enables better informed tableau backtracking and more efficient pruning. Additionally, we optimise the handling of cardinality restrictions, by introducing a strategy called pool-based merging.We empirically evaluate the proposed optimisations within the novel reasoning system Konclude and show that the proposed optimisations indeed result in significant performance improvements. More... »

PAGES

514-529

Book

TITLE

Automated Reasoning

ISBN

978-3-642-31364-6
978-3-642-31365-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31365-3_40

DOI

http://dx.doi.org/10.1007/978-3-642-31365-3_40

DIMENSIONS

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


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": "Ulm University, Ulm, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Ulm University, Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Steigmiller", 
        "givenName": "Andreas", 
        "id": "sg:person.013641624343.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013641624343.88"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "derivo GmbH, Ulm, Germany", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "derivo GmbH, Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liebig", 
        "givenName": "Thorsten", 
        "id": "sg:person.014437204743.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014437204743.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Ulm University, Ulm, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Ulm University, Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Glimm", 
        "givenName": "Birte", 
        "id": "sg:person.015234565343.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015234565343.35"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "With this contribution we push the boundary of some known optimisations such as caching to the very expressive Description Logic \\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{SROIQ}$\\end{document}. The developed method is based on a sophisticated dependency management and a precise unsatisfiability caching technique, which further enables better informed tableau backtracking and more efficient pruning. Additionally, we optimise the handling of cardinality restrictions, by introducing a strategy called pool-based merging.We empirically evaluate the proposed optimisations within the novel reasoning system Konclude and show that the proposed optimisations indeed result in significant performance improvements.", 
    "editor": [
      {
        "familyName": "Gramlich", 
        "givenName": "Bernhard", 
        "type": "Person"
      }, 
      {
        "familyName": "Miller", 
        "givenName": "Dale", 
        "type": "Person"
      }, 
      {
        "familyName": "Sattler", 
        "givenName": "Uli", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31365-3_40", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31364-6", 
        "978-3-642-31365-3"
      ], 
      "name": "Automated Reasoning", 
      "type": "Book"
    }, 
    "keywords": [
      "optimization", 
      "performance improvement", 
      "significant performance improvement", 
      "expressive description logics", 
      "boundaries", 
      "merging", 
      "method", 
      "technique", 
      "handling", 
      "logic", 
      "improvement", 
      "contribution", 
      "description logics", 
      "strategies", 
      "dependency management", 
      "restriction", 
      "backtracking", 
      "management", 
      "pruning", 
      "unsatisfiability", 
      "efficient pruning", 
      "cardinality restrictions", 
      "caching", 
      "backjumping"
    ], 
    "name": "Extended Caching, Backjumping and Merging for Expressive Description Logics", 
    "pagination": "514-529", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1020808054"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31365-3_40"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31365-3_40", 
      "https://app.dimensions.ai/details/publication/pub.1020808054"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:31", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_274.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-31365-3_40"
  }
]
 

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-642-31365-3_40'

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-642-31365-3_40'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31365-3_40'

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-642-31365-3_40'


 

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

111 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31365-3_40 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N943179347eb54ed4bfaf2655a96a475d
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description With this contribution we push the boundary of some known optimisations such as caching to the very expressive Description Logic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SROIQ}$\end{document}. The developed method is based on a sophisticated dependency management and a precise unsatisfiability caching technique, which further enables better informed tableau backtracking and more efficient pruning. Additionally, we optimise the handling of cardinality restrictions, by introducing a strategy called pool-based merging.We empirically evaluate the proposed optimisations within the novel reasoning system Konclude and show that the proposed optimisations indeed result in significant performance improvements.
7 schema:editor N727dcc0f38f24d0297687359cb46a299
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ndf5aa6a9024e4c70a9c9b12f8b45223d
12 schema:keywords backjumping
13 backtracking
14 boundaries
15 caching
16 cardinality restrictions
17 contribution
18 dependency management
19 description logics
20 efficient pruning
21 expressive description logics
22 handling
23 improvement
24 logic
25 management
26 merging
27 method
28 optimization
29 performance improvement
30 pruning
31 restriction
32 significant performance improvement
33 strategies
34 technique
35 unsatisfiability
36 schema:name Extended Caching, Backjumping and Merging for Expressive Description Logics
37 schema:pagination 514-529
38 schema:productId Nfce9a98a06cf411c9afd1728d4db1a9c
39 Nfd2452bdcb6f4bf5b9997a79fa70227e
40 schema:publisher N9f935893f61240389dc19929bfed1c16
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020808054
42 https://doi.org/10.1007/978-3-642-31365-3_40
43 schema:sdDatePublished 2022-06-01T22:31
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N2a14d580806e433180c6f0aae6f63593
46 schema:url https://doi.org/10.1007/978-3-642-31365-3_40
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N03fbbdf62dd544f7a806174e0c960b70 rdf:first N453bae1a04264e78a001830af3dc9877
51 rdf:rest N638d62612ffc4a8baf541e66bc454b7a
52 N07dd2bbda463496fb27039e422adda9c rdf:first sg:person.015234565343.35
53 rdf:rest rdf:nil
54 N2641cd5c8a0242909b0b74f02f75cfb2 schema:familyName Sattler
55 schema:givenName Uli
56 rdf:type schema:Person
57 N2a14d580806e433180c6f0aae6f63593 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N453bae1a04264e78a001830af3dc9877 schema:familyName Miller
60 schema:givenName Dale
61 rdf:type schema:Person
62 N638d62612ffc4a8baf541e66bc454b7a rdf:first N2641cd5c8a0242909b0b74f02f75cfb2
63 rdf:rest rdf:nil
64 N727dcc0f38f24d0297687359cb46a299 rdf:first N917079515f834fe48dd53bb7e4c0fb46
65 rdf:rest N03fbbdf62dd544f7a806174e0c960b70
66 N87d8011a88be4f4e8e251e95fa66aee1 rdf:first sg:person.014437204743.19
67 rdf:rest N07dd2bbda463496fb27039e422adda9c
68 N917079515f834fe48dd53bb7e4c0fb46 schema:familyName Gramlich
69 schema:givenName Bernhard
70 rdf:type schema:Person
71 N943179347eb54ed4bfaf2655a96a475d rdf:first sg:person.013641624343.88
72 rdf:rest N87d8011a88be4f4e8e251e95fa66aee1
73 N9f935893f61240389dc19929bfed1c16 schema:name Springer Nature
74 rdf:type schema:Organisation
75 Ndf5aa6a9024e4c70a9c9b12f8b45223d schema:isbn 978-3-642-31364-6
76 978-3-642-31365-3
77 schema:name Automated Reasoning
78 rdf:type schema:Book
79 Nfce9a98a06cf411c9afd1728d4db1a9c schema:name doi
80 schema:value 10.1007/978-3-642-31365-3_40
81 rdf:type schema:PropertyValue
82 Nfd2452bdcb6f4bf5b9997a79fa70227e schema:name dimensions_id
83 schema:value pub.1020808054
84 rdf:type schema:PropertyValue
85 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
86 schema:name Psychology and Cognitive Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
89 schema:name Psychology
90 rdf:type schema:DefinedTerm
91 sg:person.013641624343.88 schema:affiliation grid-institutes:grid.6582.9
92 schema:familyName Steigmiller
93 schema:givenName Andreas
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013641624343.88
95 rdf:type schema:Person
96 sg:person.014437204743.19 schema:affiliation grid-institutes:None
97 schema:familyName Liebig
98 schema:givenName Thorsten
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014437204743.19
100 rdf:type schema:Person
101 sg:person.015234565343.35 schema:affiliation grid-institutes:grid.6582.9
102 schema:familyName Glimm
103 schema:givenName Birte
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015234565343.35
105 rdf:type schema:Person
106 grid-institutes:None schema:alternateName derivo GmbH, Ulm, Germany
107 schema:name derivo GmbH, Ulm, Germany
108 rdf:type schema:Organization
109 grid-institutes:grid.6582.9 schema:alternateName Ulm University, Ulm, Germany
110 schema:name Ulm University, Ulm, Germany
111 rdf:type schema:Organization
 




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


...