# Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning

Ontology type: schema:Chapter

### Chapter Info

DATE

2012

AUTHORS ABSTRACT

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. More... »

PAGES

13-14

### Book

TITLE

Logic for Programming, Artificial Intelligence, and Reasoning

ISBN

978-3-642-28716-9
978-3-642-28717-6

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-28717-6_3

DOI

http://dx.doi.org/10.1007/978-3-642-28717-6_3

DIMENSIONS

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

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:

[
{
"@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:

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-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

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

...