Ontology type: schema:Chapter Open Access: True
2008
AUTHORS ABSTRACTWe 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... »
PAGES391-405
Logic for Programming, Artificial Intelligence, and Reasoning
ISBN
978-3-540-89438-4
978-3-540-89439-1
http://scigraph.springernature.com/pub.10.1007/978-3-540-89439-1_28
DOIhttp://dx.doi.org/10.1007/978-3-540-89439-1_28
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1003282452
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
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 |