On the Krom Extension of View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-11-22

AUTHORS

David Toman , Grant Weddell

ABSTRACT

We consider the consequences on basic reasoning problems of the Krom extension to the description logic dialect \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {CFDI}^{\forall -}_{nc}$$\end{document}, that is, of allowing negated primitive concepts on left-hand-sides of inclusion dependencies. Specifically, we show that TBox consistency and concept satisfiability remain in PTIME, but that this extension leads to intractability for both knowledge base consistency and instance retrieval. We then trace the roots of intractability by presenting tight conditions that recover PTIME complexity for both of these problems. The conditions relate to the structure of functional constraints in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {CFDI}^{\forall -}_{nc}$$\end{document} and to the unique name assumption. More... »

PAGES

559-571

Book

TITLE

AI 2015: Advances in Artificial Intelligence

ISBN

978-3-319-26349-6
978-3-319-26350-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-26350-2_50

DOI

http://dx.doi.org/10.1007/978-3-319-26350-2_50

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Toman", 
        "givenName": "David", 
        "id": "sg:person.011644611743.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011644611743.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weddell", 
        "givenName": "Grant", 
        "id": "sg:person.01111756132.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-11-22", 
    "datePublishedReg": "2015-11-22", 
    "description": "We consider the consequences on basic reasoning problems of the Krom extension to the description logic dialect \\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 {CFDI}^{\\forall -}_{nc}$$\\end{document}, that is, of allowing negated primitive concepts on left-hand-sides of inclusion dependencies. Specifically, we show that TBox consistency and concept satisfiability remain in PTIME, but that this extension leads to intractability for both knowledge base consistency and instance retrieval. We then trace the roots of intractability by presenting tight conditions that recover PTIME complexity for both of these problems. The conditions relate to the structure of functional constraints in \\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 {CFDI}^{\\forall -}_{nc}$$\\end{document} and to the unique name assumption.", 
    "editor": [
      {
        "familyName": "Pfahringer", 
        "givenName": "Bernhard", 
        "type": "Person"
      }, 
      {
        "familyName": "Renz", 
        "givenName": "Jochen", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-26350-2_50", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-26349-6", 
        "978-3-319-26350-2"
      ], 
      "name": "AI 2015: Advances in Artificial Intelligence", 
      "type": "Book"
    }, 
    "keywords": [
      "unique name assumption", 
      "basic reasoning problems", 
      "description logic dialect", 
      "knowledge base consistency", 
      "inclusion dependencies", 
      "instance retrieval", 
      "reasoning problems", 
      "concept satisfiability", 
      "primitive concepts", 
      "intractability", 
      "PTIME complexity", 
      "extension", 
      "satisfiability", 
      "PTIME", 
      "retrieval", 
      "tight conditions", 
      "complexity", 
      "constraints", 
      "consistency", 
      "dependency", 
      "dialects", 
      "concept", 
      "functional constraints", 
      "consequences", 
      "problem", 
      "assumption", 
      "conditions", 
      "structure", 
      "side", 
      "roots", 
      "Krom extension", 
      "logic dialect", 
      "TBox consistency", 
      "base consistency", 
      "roots of intractability", 
      "name assumption"
    ], 
    "name": "On the Krom Extension of", 
    "pagination": "559-571", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028077868"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-26350-2_50"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-26350-2_50", 
      "https://app.dimensions.ai/details/publication/pub.1028077868"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_95.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-26350-2_50"
  }
]
 

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-319-26350-2_50'

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-319-26350-2_50'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-26350-2_50'

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-319-26350-2_50'


 

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

108 TRIPLES      23 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-26350-2_50 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N12102deb29734c539f6255fd99eb7742
4 schema:datePublished 2015-11-22
5 schema:datePublishedReg 2015-11-22
6 schema:description We consider the consequences on basic reasoning problems of the Krom extension to the description logic dialect \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {CFDI}^{\forall -}_{nc}$$\end{document}, that is, of allowing negated primitive concepts on left-hand-sides of inclusion dependencies. Specifically, we show that TBox consistency and concept satisfiability remain in PTIME, but that this extension leads to intractability for both knowledge base consistency and instance retrieval. We then trace the roots of intractability by presenting tight conditions that recover PTIME complexity for both of these problems. The conditions relate to the structure of functional constraints in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {CFDI}^{\forall -}_{nc}$$\end{document} and to the unique name assumption.
7 schema:editor N6827241a15884965baf71eb6a0df6830
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Na497c83c909a4e5bb0fc1866cbd5f1bf
12 schema:keywords Krom extension
13 PTIME
14 PTIME complexity
15 TBox consistency
16 assumption
17 base consistency
18 basic reasoning problems
19 complexity
20 concept
21 concept satisfiability
22 conditions
23 consequences
24 consistency
25 constraints
26 dependency
27 description logic dialect
28 dialects
29 extension
30 functional constraints
31 inclusion dependencies
32 instance retrieval
33 intractability
34 knowledge base consistency
35 logic dialect
36 name assumption
37 primitive concepts
38 problem
39 reasoning problems
40 retrieval
41 roots
42 roots of intractability
43 satisfiability
44 side
45 structure
46 tight conditions
47 unique name assumption
48 schema:name On the Krom Extension of
49 schema:pagination 559-571
50 schema:productId N33acb52ab8af48b58b294d0da6f6846c
51 Nfd9fd7768c984e44942d18e8b8a5f07b
52 schema:publisher Nb0ceba69041249588065553e170ae6e8
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028077868
54 https://doi.org/10.1007/978-3-319-26350-2_50
55 schema:sdDatePublished 2021-12-01T20:13
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Nc9a2adec77fd413cbd50aa8ade20fbe9
58 schema:url https://doi.org/10.1007/978-3-319-26350-2_50
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N0a22627b13f249ce9b880c3ed83c754a schema:familyName Renz
63 schema:givenName Jochen
64 rdf:type schema:Person
65 N12102deb29734c539f6255fd99eb7742 rdf:first sg:person.011644611743.11
66 rdf:rest N906dca3aeaa2444eacbeecb4a7a0e5d8
67 N33acb52ab8af48b58b294d0da6f6846c schema:name doi
68 schema:value 10.1007/978-3-319-26350-2_50
69 rdf:type schema:PropertyValue
70 N6827241a15884965baf71eb6a0df6830 rdf:first N6b05be0e78fd44fdb698fcba19625fc1
71 rdf:rest Nc08236d4af0b4de99fa66ce3fb8a1e20
72 N6b05be0e78fd44fdb698fcba19625fc1 schema:familyName Pfahringer
73 schema:givenName Bernhard
74 rdf:type schema:Person
75 N906dca3aeaa2444eacbeecb4a7a0e5d8 rdf:first sg:person.01111756132.29
76 rdf:rest rdf:nil
77 Na497c83c909a4e5bb0fc1866cbd5f1bf schema:isbn 978-3-319-26349-6
78 978-3-319-26350-2
79 schema:name AI 2015: Advances in Artificial Intelligence
80 rdf:type schema:Book
81 Nb0ceba69041249588065553e170ae6e8 schema:name Springer Nature
82 rdf:type schema:Organisation
83 Nc08236d4af0b4de99fa66ce3fb8a1e20 rdf:first N0a22627b13f249ce9b880c3ed83c754a
84 rdf:rest rdf:nil
85 Nc9a2adec77fd413cbd50aa8ade20fbe9 schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 Nfd9fd7768c984e44942d18e8b8a5f07b schema:name dimensions_id
88 schema:value pub.1028077868
89 rdf:type schema:PropertyValue
90 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
91 schema:name Psychology and Cognitive Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
94 schema:name Psychology
95 rdf:type schema:DefinedTerm
96 sg:person.01111756132.29 schema:affiliation grid-institutes:grid.46078.3d
97 schema:familyName Weddell
98 schema:givenName Grant
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29
100 rdf:type schema:Person
101 sg:person.011644611743.11 schema:affiliation grid-institutes:grid.46078.3d
102 schema:familyName Toman
103 schema:givenName David
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011644611743.11
105 rdf:type schema:Person
106 grid-institutes:grid.46078.3d schema:alternateName Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
107 schema:name Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
108 rdf:type schema:Organization
 




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


...