Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Boris Motik

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: 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", 
      "knowledge base", 
      "description logic reasoning", 
      "worst-case complexity", 
      "logic reasoning", 
      "knowledge bases", 
      "individual knowledge base", 
      "complexity results", 
      "parameter tractability", 
      "KR formalisms", 
      "worst-case complexity results", 
      "reasoning problems", 
      "parameterized complexity", 
      "exponential time", 
      "basic description logic", 
      "complexity", 
      "reasoning", 
      "logic", 
      "coarse measure", 
      "constructors", 
      "tractability", 
      "important goal", 
      "base", 
      "Such results", 
      "measures", 
      "goal", 
      "research", 
      "axioms", 
      "same size", 
      "formalism", 
      "example", 
      "way", 
      "results", 
      "time", 
      "interaction", 
      "whole", 
      "problem", 
      "basis", 
      "size", 
      "kb", 
      "hardness", 
      "logic-based KR formalisms"
    ], 
    "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-01-01T19:23", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_404.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

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.

107 TRIPLES      23 PREDICATES      68 URIs      61 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 N1fc2d27446a34945b6b83328e2e9799c
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 Nb96fc83ab1fa4578a1333ffdc5acf20e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nd88151d434734c1a8adc5fd1caef93a0
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 knowledge base
31 interaction
32 kb
33 knowledge base
34 knowledge bases
35 logic
36 logic reasoning
37 logic-based KR formalisms
38 measures
39 parameter tractability
40 parameterized complexity
41 problem
42 reasoning
43 reasoning problems
44 research
45 results
46 same size
47 size
48 time
49 tractability
50 way
51 whole
52 worst-case complexity
53 worst-case complexity results
54 schema:name Parameterized Complexity and Fixed-Parameter Tractability of Description Logic Reasoning
55 schema:pagination 13-14
56 schema:productId N72c807a095bb4579b39db0fc6409230c
57 Nadfc0b7e14bd4511b8b43e3c605c5355
58 schema:publisher Nfce68e87629e404a86aaed058e8eb0aa
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019752486
60 https://doi.org/10.1007/978-3-642-28717-6_3
61 schema:sdDatePublished 2022-01-01T19:23
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N69908e79c4294adc9e778122823febcc
64 schema:url https://doi.org/10.1007/978-3-642-28717-6_3
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N04e716437f334ac9805b55bcd86c5c46 rdf:first Ne4590c762d3d4e57b78588a5a8e521f3
69 rdf:rest rdf:nil
70 N1fc2d27446a34945b6b83328e2e9799c rdf:first sg:person.07401076267.36
71 rdf:rest rdf:nil
72 N69908e79c4294adc9e778122823febcc schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N72c807a095bb4579b39db0fc6409230c schema:name doi
75 schema:value 10.1007/978-3-642-28717-6_3
76 rdf:type schema:PropertyValue
77 Nadfc0b7e14bd4511b8b43e3c605c5355 schema:name dimensions_id
78 schema:value pub.1019752486
79 rdf:type schema:PropertyValue
80 Nb96fc83ab1fa4578a1333ffdc5acf20e rdf:first Ne24fc1003b974448902316849984343d
81 rdf:rest N04e716437f334ac9805b55bcd86c5c46
82 Nd88151d434734c1a8adc5fd1caef93a0 schema:isbn 978-3-642-28716-9
83 978-3-642-28717-6
84 schema:name Logic for Programming, Artificial Intelligence, and Reasoning
85 rdf:type schema:Book
86 Ne24fc1003b974448902316849984343d schema:familyName Bjørner
87 schema:givenName Nikolaj
88 rdf:type schema:Person
89 Ne4590c762d3d4e57b78588a5a8e521f3 schema:familyName Voronkov
90 schema:givenName Andrei
91 rdf:type schema:Person
92 Nfce68e87629e404a86aaed058e8eb0aa schema:name Springer Nature
93 rdf:type schema:Organisation
94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
95 schema:name Information and Computing Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
98 schema:name Computation Theory and Mathematics
99 rdf:type schema:DefinedTerm
100 sg:person.07401076267.36 schema:affiliation grid-institutes:grid.4991.5
101 schema:familyName Motik
102 schema:givenName Boris
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401076267.36
104 rdf:type schema:Person
105 grid-institutes:grid.4991.5 schema:alternateName Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK
106 schema:name Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK
107 rdf:type schema:Organization
 




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


...