Role Conjunctions in Expressive Description Logics View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Birte Glimm , Yevgeny Kazakov

ABSTRACT

We show that adding role conjunctions to the Description Logics (DLs) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SHI}$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SHOIF}$\end{document} causes a jump in the computational complexity of the standard reasoning tasks from ExpTime-complete to 2ExpTime-complete and from NExpTime-complete to N2ExpTime-hard respectively. We further show that this increase is due to a subtle interaction between inverse roles, role hierarchies, and role transitivity in the presence of role conjunctions and that for 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{SHQ}$\end{document} a jump in the computational complexity cannot be observed. More... »

PAGES

391-405

Book

TITLE

Logic for Programming, Artificial Intelligence, and Reasoning

ISBN

978-3-540-89438-4
978-3-540-89439-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-89439-1_28

DOI

http://dx.doi.org/10.1007/978-3-540-89439-1_28

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Oxford University Computing Laboratory, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Oxford University Computing Laboratory, UK"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Oxford University Computing Laboratory, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Oxford University Computing Laboratory, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kazakov", 
        "givenName": "Yevgeny", 
        "id": "sg:person.013173133226.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013173133226.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "We show that adding role conjunctions to the Description Logics (DLs) \\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{SHI}$\\end{document} and \\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{SHOIF}$\\end{document} causes a jump in the computational complexity of the standard reasoning tasks from ExpTime-complete to 2ExpTime-complete and from NExpTime-complete to N2ExpTime-hard respectively. We further show that this increase is due to a subtle interaction between inverse roles, role hierarchies, and role transitivity in the presence of role conjunctions and that for 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{SHQ}$\\end{document} a jump in the computational complexity cannot be observed.", 
    "editor": [
      {
        "familyName": "Cervesato", 
        "givenName": "Iliano", 
        "type": "Person"
      }, 
      {
        "familyName": "Veith", 
        "givenName": "Helmut", 
        "type": "Person"
      }, 
      {
        "familyName": "Voronkov", 
        "givenName": "Andrei", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-89439-1_28", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-89438-4", 
        "978-3-540-89439-1"
      ], 
      "name": "Logic for Programming, Artificial Intelligence, and Reasoning", 
      "type": "Book"
    }, 
    "keywords": [
      "standard reasoning tasks", 
      "reasoning tasks", 
      "task", 
      "inverse roles", 
      "expressive description logics", 
      "subtle interactions", 
      "role hierarchy", 
      "transitivity", 
      "description logics", 
      "complexity", 
      "hierarchy", 
      "interaction", 
      "conjunction", 
      "role", 
      "logic", 
      "computational complexity", 
      "increase", 
      "presence", 
      "EXPTIME", 
      "jump"
    ], 
    "name": "Role Conjunctions in Expressive Description Logics", 
    "pagination": "391-405", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003282452"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-89439-1_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-89439-1_28", 
      "https://app.dimensions.ai/details/publication/pub.1003282452"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:27", 
    "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_110.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-89439-1_28"
  }
]
 

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-89439-1_28'

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-89439-1_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-89439-1_28'

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-89439-1_28'


 

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

97 TRIPLES      23 PREDICATES      46 URIs      39 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-89439-1_28 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd8bb3a3cc10441feb1a3b32b4ad3186d
4 schema:datePublished 2008
5 schema:datePublishedReg 2008-01-01
6 schema:description We show that adding role conjunctions to the Description Logics (DLs) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SHI}$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{SHOIF}$\end{document} causes a jump in the computational complexity of the standard reasoning tasks from ExpTime-complete to 2ExpTime-complete and from NExpTime-complete to N2ExpTime-hard respectively. We further show that this increase is due to a subtle interaction between inverse roles, role hierarchies, and role transitivity in the presence of role conjunctions and that for 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{SHQ}$\end{document} a jump in the computational complexity cannot be observed.
7 schema:editor Nbf41663fa4984dc0baed4de9fee94aa3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nd44f72841e2f432da03fc1e31dadb8d2
12 schema:keywords EXPTIME
13 complexity
14 computational complexity
15 conjunction
16 description logics
17 expressive description logics
18 hierarchy
19 increase
20 interaction
21 inverse roles
22 jump
23 logic
24 presence
25 reasoning tasks
26 role
27 role hierarchy
28 standard reasoning tasks
29 subtle interactions
30 task
31 transitivity
32 schema:name Role Conjunctions in Expressive Description Logics
33 schema:pagination 391-405
34 schema:productId N74a485fb82824546abe40b9ed2d2bc61
35 Nf4a0a4ef3b8c4baea2c74dd7ed6bd661
36 schema:publisher Nd86b2478a0cb49b18c752f6034c13cab
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003282452
38 https://doi.org/10.1007/978-3-540-89439-1_28
39 schema:sdDatePublished 2022-06-01T22:27
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher N9e88b476c7ad451daa5abd621fc1e1fe
42 schema:url https://doi.org/10.1007/978-3-540-89439-1_28
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N0041c64285834e938092864917cbc12f rdf:first Nc6b46c087b5d462e85025dd8991b51d6
47 rdf:rest N2fe0c67b95d0471babe94f7625a1458d
48 N01d0ec3531764c418e6f9b0f58a51db9 schema:familyName Voronkov
49 schema:givenName Andrei
50 rdf:type schema:Person
51 N0d6dc68b401e4227b51cdf84fe3d1af1 rdf:first sg:person.013173133226.01
52 rdf:rest rdf:nil
53 N2fe0c67b95d0471babe94f7625a1458d rdf:first N01d0ec3531764c418e6f9b0f58a51db9
54 rdf:rest rdf:nil
55 N535cbeee67c844c8bbffea01b629049d schema:familyName Cervesato
56 schema:givenName Iliano
57 rdf:type schema:Person
58 N74a485fb82824546abe40b9ed2d2bc61 schema:name doi
59 schema:value 10.1007/978-3-540-89439-1_28
60 rdf:type schema:PropertyValue
61 N9e88b476c7ad451daa5abd621fc1e1fe schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 Nbf41663fa4984dc0baed4de9fee94aa3 rdf:first N535cbeee67c844c8bbffea01b629049d
64 rdf:rest N0041c64285834e938092864917cbc12f
65 Nc6b46c087b5d462e85025dd8991b51d6 schema:familyName Veith
66 schema:givenName Helmut
67 rdf:type schema:Person
68 Nd44f72841e2f432da03fc1e31dadb8d2 schema:isbn 978-3-540-89438-4
69 978-3-540-89439-1
70 schema:name Logic for Programming, Artificial Intelligence, and Reasoning
71 rdf:type schema:Book
72 Nd86b2478a0cb49b18c752f6034c13cab schema:name Springer Nature
73 rdf:type schema:Organisation
74 Nd8bb3a3cc10441feb1a3b32b4ad3186d rdf:first sg:person.015234565343.35
75 rdf:rest N0d6dc68b401e4227b51cdf84fe3d1af1
76 Nf4a0a4ef3b8c4baea2c74dd7ed6bd661 schema:name dimensions_id
77 schema:value pub.1003282452
78 rdf:type schema:PropertyValue
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
83 schema:name Computation Theory and Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.013173133226.01 schema:affiliation grid-institutes:grid.4991.5
86 schema:familyName Kazakov
87 schema:givenName Yevgeny
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013173133226.01
89 rdf:type schema:Person
90 sg:person.015234565343.35 schema:affiliation grid-institutes:grid.4991.5
91 schema:familyName Glimm
92 schema:givenName Birte
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015234565343.35
94 rdf:type schema:Person
95 grid-institutes:grid.4991.5 schema:alternateName Oxford University Computing Laboratory, UK
96 schema:name Oxford University Computing Laboratory, UK
97 rdf:type schema:Organization
 




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


...