Ontology type: schema:Chapter
2012
AUTHORS ABSTRACTAn important goal of research in description logics (DLs) and related logic-based KR formalisms is to identify the worst-case complexity of reasoning. Such results, however, measure the complexity of a logic as a whole. For example, reasoning in the basic DL \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ALCI}$\end{document} is ExpTime-complete, which means that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ALCI}$\end{document} constructors can be used in a way so that exponential time is strictly required for solving a reasoning problem. It is, however, well known that, given two \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ALCI}$\end{document} knowledge bases of roughly the same size, reasoning with one knowledge base may be much more difficult than with the other, depending on the interaction of the axioms in the KBs. Thus, existing worst-case complexity results provide only a very coarse measure of reasoning complexity, and they do not tell us much about the “hardness” of each individual knowledge base. More... »
PAGES13-14
Logic for Programming, Artificial Intelligence, and Reasoning
ISBN
978-3-642-28716-9
978-3-642-28717-6
http://scigraph.springernature.com/pub.10.1007/978-3-642-28717-6_3
DOIhttp://dx.doi.org/10.1007/978-3-642-28717-6_3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1019752486
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": "Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK",
"id": "http://www.grid.ac/institutes/grid.4991.5",
"name": [
"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, 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"
}
],
"datePublished": "2012",
"datePublishedReg": "2012-01-01",
"description": "An important goal of research in description logics (DLs) and related logic-based KR formalisms is to identify the worst-case complexity of reasoning. Such results, however, measure the complexity of a logic as a whole. For example, reasoning in the basic 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{ALCI}$\\end{document} is ExpTime-complete, which means that \\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{ALCI}$\\end{document} constructors can be used in a way so that exponential time is strictly required for solving a reasoning problem. It is, however, well known that, given two \\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{ALCI}$\\end{document} knowledge bases of roughly the same size, reasoning with one knowledge base may be much more difficult than with the other, depending on the interaction of the axioms in the KBs. Thus, existing worst-case complexity results provide only a very coarse measure of reasoning complexity, and they do not tell us much about the \u201chardness\u201d of each individual knowledge base.",
"editor": [
{
"familyName": "Bj\u00f8rner",
"givenName": "Nikolaj",
"type": "Person"
},
{
"familyName": "Voronkov",
"givenName": "Andrei",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-28717-6_3",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-28716-9",
"978-3-642-28717-6"
],
"name": "Logic for Programming, Artificial Intelligence, and Reasoning",
"type": "Book"
},
"keywords": [
"description logics",
"individual's knowledge base",
"reasoning problems",
"knowledge base",
"description logic reasoning",
"worst-case complexity",
"worst-case complexity results",
"logic reasoning",
"knowledge bases",
"KR formalisms",
"complexity results",
"reasoning",
"parameter tractability",
"exponential time",
"parameterized complexity",
"basic description logic",
"complexity",
"coarse measure",
"important goal",
"logic",
"measures",
"Such results",
"research",
"constructors",
"tractability",
"goal",
"base",
"results",
"way",
"interaction",
"axioms",
"formalism",
"same size",
"whole",
"example",
"problem",
"basis",
"time",
"size",
"kb",
"hardness"
],
"name": "Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning",
"pagination": "13-14",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1019752486"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-28717-6_3"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-28717-6_3",
"https://app.dimensions.ai/details/publication/pub.1019752486"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:46",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_356.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-28717-6_3"
}
]
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-642-28717-6_3'
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-28717-6_3'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-28717-6_3'
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-28717-6_3'
This table displays all metadata directly associated to this object as RDF triples.
106 TRIPLES
23 PREDICATES
67 URIs
60 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-642-28717-6_3 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0802 |
3 | ″ | schema:author | N9f30895c60de49398e32b122440d7e11 |
4 | ″ | schema:datePublished | 2012 |
5 | ″ | schema:datePublishedReg | 2012-01-01 |
6 | ″ | schema:description | An important goal of research in description logics (DLs) and related logic-based KR formalisms is to identify the worst-case complexity of reasoning. Such results, however, measure the complexity of a logic as a whole. For example, reasoning in the basic DL \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ALCI}$\end{document} is ExpTime-complete, which means that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ALCI}$\end{document} constructors can be used in a way so that exponential time is strictly required for solving a reasoning problem. It is, however, well known that, given two \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{ALCI}$\end{document} knowledge bases of roughly the same size, reasoning with one knowledge base may be much more difficult than with the other, depending on the interaction of the axioms in the KBs. Thus, existing worst-case complexity results provide only a very coarse measure of reasoning complexity, and they do not tell us much about the “hardness” of each individual knowledge base. |
7 | ″ | schema:editor | Nf648e4be20e945ab8ea932704d77eabf |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | false |
11 | ″ | schema:isPartOf | N58484ab677c34d8285cbf527e44959ec |
12 | ″ | schema:keywords | KR formalisms |
13 | ″ | ″ | Such results |
14 | ″ | ″ | axioms |
15 | ″ | ″ | base |
16 | ″ | ″ | basic description logic |
17 | ″ | ″ | basis |
18 | ″ | ″ | coarse measure |
19 | ″ | ″ | complexity |
20 | ″ | ″ | complexity results |
21 | ″ | ″ | constructors |
22 | ″ | ″ | description logic reasoning |
23 | ″ | ″ | description logics |
24 | ″ | ″ | example |
25 | ″ | ″ | exponential time |
26 | ″ | ″ | formalism |
27 | ″ | ″ | goal |
28 | ″ | ″ | hardness |
29 | ″ | ″ | important goal |
30 | ″ | ″ | individual's knowledge base |
31 | ″ | ″ | interaction |
32 | ″ | ″ | kb |
33 | ″ | ″ | knowledge base |
34 | ″ | ″ | knowledge bases |
35 | ″ | ″ | logic |
36 | ″ | ″ | logic reasoning |
37 | ″ | ″ | measures |
38 | ″ | ″ | parameter tractability |
39 | ″ | ″ | parameterized complexity |
40 | ″ | ″ | problem |
41 | ″ | ″ | reasoning |
42 | ″ | ″ | reasoning problems |
43 | ″ | ″ | research |
44 | ″ | ″ | results |
45 | ″ | ″ | same size |
46 | ″ | ″ | size |
47 | ″ | ″ | time |
48 | ″ | ″ | tractability |
49 | ″ | ″ | way |
50 | ″ | ″ | whole |
51 | ″ | ″ | worst-case complexity |
52 | ″ | ″ | worst-case complexity results |
53 | ″ | schema:name | Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning |
54 | ″ | schema:pagination | 13-14 |
55 | ″ | schema:productId | Ncb703a373f5f42b98b8df8ef1ed18029 |
56 | ″ | ″ | Nd990ce8842fd4206b10199f673081acf |
57 | ″ | schema:publisher | Nb2870b552a4d4beab6c1ce675f5f2309 |
58 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1019752486 |
59 | ″ | ″ | https://doi.org/10.1007/978-3-642-28717-6_3 |
60 | ″ | schema:sdDatePublished | 2022-05-20T07:46 |
61 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
62 | ″ | schema:sdPublisher | N7b1c76d5f2254e5cac53df5d53033bcb |
63 | ″ | schema:url | https://doi.org/10.1007/978-3-642-28717-6_3 |
64 | ″ | sgo:license | sg:explorer/license/ |
65 | ″ | sgo:sdDataset | chapters |
66 | ″ | rdf:type | schema:Chapter |
67 | N58484ab677c34d8285cbf527e44959ec | schema:isbn | 978-3-642-28716-9 |
68 | ″ | ″ | 978-3-642-28717-6 |
69 | ″ | schema:name | Logic for Programming, Artificial Intelligence, and Reasoning |
70 | ″ | rdf:type | schema:Book |
71 | N7b1c76d5f2254e5cac53df5d53033bcb | schema:name | Springer Nature - SN SciGraph project |
72 | ″ | rdf:type | schema:Organization |
73 | N9f30895c60de49398e32b122440d7e11 | rdf:first | sg:person.07401076267.36 |
74 | ″ | rdf:rest | rdf:nil |
75 | Na387840b2bc84d33821e3277b6d39993 | rdf:first | Ned993b604774494ab599464dcfe70aa8 |
76 | ″ | rdf:rest | rdf:nil |
77 | Nb2870b552a4d4beab6c1ce675f5f2309 | schema:name | Springer Nature |
78 | ″ | rdf:type | schema:Organisation |
79 | Nb70fb9ce7fda4e57afcbb57cd1a29e7e | schema:familyName | Bjørner |
80 | ″ | schema:givenName | Nikolaj |
81 | ″ | rdf:type | schema:Person |
82 | Ncb703a373f5f42b98b8df8ef1ed18029 | schema:name | dimensions_id |
83 | ″ | schema:value | pub.1019752486 |
84 | ″ | rdf:type | schema:PropertyValue |
85 | Nd990ce8842fd4206b10199f673081acf | schema:name | doi |
86 | ″ | schema:value | 10.1007/978-3-642-28717-6_3 |
87 | ″ | rdf:type | schema:PropertyValue |
88 | Ned993b604774494ab599464dcfe70aa8 | schema:familyName | Voronkov |
89 | ″ | schema:givenName | Andrei |
90 | ″ | rdf:type | schema:Person |
91 | Nf648e4be20e945ab8ea932704d77eabf | rdf:first | Nb70fb9ce7fda4e57afcbb57cd1a29e7e |
92 | ″ | rdf:rest | Na387840b2bc84d33821e3277b6d39993 |
93 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
94 | ″ | schema:name | Information and Computing Sciences |
95 | ″ | rdf:type | schema:DefinedTerm |
96 | anzsrc-for:0802 | schema:inDefinedTermSet | anzsrc-for: |
97 | ″ | schema:name | Computation Theory and Mathematics |
98 | ″ | rdf:type | schema:DefinedTerm |
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 | Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK |
105 | ″ | schema:name | Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK |
106 | ″ | rdf:type | schema:Organization |