Implementation of Logical Retraction in Constraint Handling Rules with Justifications View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-09-27

AUTHORS

Thom Frühwirth

ABSTRACT

In previous work we added justifications to Constraint Handling Rules (CHR) to enable logical retraction of constraints for dynamic algorithms. We presented a straightforward source-to-source transformation to implement this conservative extension. In this companion paper, we improve the performance of the transformation. We discuss its worst-case time complexity in general. Then we perform experiments. We benchmark the dynamic problem of maintaining shortest paths under addition and retraction of paths. The results validate our complexity considerations. More... »

PAGES

37-52

Book

TITLE

Declarative Programming and Knowledge Management

ISBN

978-3-030-00800-0
978-3-030-00801-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-00801-7_3

DOI

http://dx.doi.org/10.1007/978-3-030-00801-7_3

DIMENSIONS

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


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": "Ulm University, Ulm, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Ulm University, Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fr\u00fchwirth", 
        "givenName": "Thom", 
        "id": "sg:person.013750414271.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-09-27", 
    "datePublishedReg": "2018-09-27", 
    "description": "In previous work we added justifications to Constraint Handling Rules (CHR) to enable logical retraction of constraints for dynamic algorithms. We presented a straightforward source-to-source transformation to implement this conservative extension. In this companion paper, we improve the performance of the transformation. We discuss its worst-case time complexity in general. Then we perform experiments. We benchmark the dynamic problem of maintaining shortest paths under addition and retraction of paths. The results validate our complexity considerations.", 
    "editor": [
      {
        "familyName": "Seipel", 
        "givenName": "Dietmar", 
        "type": "Person"
      }, 
      {
        "familyName": "Hanus", 
        "givenName": "Michael", 
        "type": "Person"
      }, 
      {
        "familyName": "Abreu", 
        "givenName": "Salvador", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-00801-7_3", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-00800-0", 
        "978-3-030-00801-7"
      ], 
      "name": "Declarative Programming and Knowledge Management", 
      "type": "Book"
    }, 
    "keywords": [
      "Constraint Handling Rules", 
      "Handling Rules", 
      "worst-case time complexity", 
      "time complexity", 
      "source transformation", 
      "complexity considerations", 
      "shortest path", 
      "dynamic algorithm", 
      "straightforward source", 
      "conservative extension", 
      "previous work", 
      "dynamic problems", 
      "rules", 
      "algorithm", 
      "path", 
      "complexity", 
      "implementation", 
      "constraints", 
      "performance", 
      "extension", 
      "work", 
      "transformation", 
      "experiments", 
      "companion paper", 
      "justification", 
      "results", 
      "consideration", 
      "source", 
      "addition", 
      "retraction", 
      "paper", 
      "problem", 
      "logical retraction", 
      "retraction of paths"
    ], 
    "name": "Implementation of Logical Retraction in Constraint Handling Rules with Justifications", 
    "pagination": "37-52", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107244329"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-00801-7_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-00801-7_3", 
      "https://app.dimensions.ai/details/publication/pub.1107244329"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_270.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-00801-7_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-030-00801-7_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-030-00801-7_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-00801-7_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-030-00801-7_3'


 

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

104 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-00801-7_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N99131994df734e61ad5d141eb4a8a1f5
4 schema:datePublished 2018-09-27
5 schema:datePublishedReg 2018-09-27
6 schema:description In previous work we added justifications to Constraint Handling Rules (CHR) to enable logical retraction of constraints for dynamic algorithms. We presented a straightforward source-to-source transformation to implement this conservative extension. In this companion paper, we improve the performance of the transformation. We discuss its worst-case time complexity in general. Then we perform experiments. We benchmark the dynamic problem of maintaining shortest paths under addition and retraction of paths. The results validate our complexity considerations.
7 schema:editor N94dec6291a9c44328f3625d10f3b1fc7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne674333757444638b6f4f848006fe3a4
12 schema:keywords Constraint Handling Rules
13 Handling Rules
14 addition
15 algorithm
16 companion paper
17 complexity
18 complexity considerations
19 conservative extension
20 consideration
21 constraints
22 dynamic algorithm
23 dynamic problems
24 experiments
25 extension
26 implementation
27 justification
28 logical retraction
29 paper
30 path
31 performance
32 previous work
33 problem
34 results
35 retraction
36 retraction of paths
37 rules
38 shortest path
39 source
40 source transformation
41 straightforward source
42 time complexity
43 transformation
44 work
45 worst-case time complexity
46 schema:name Implementation of Logical Retraction in Constraint Handling Rules with Justifications
47 schema:pagination 37-52
48 schema:productId N0392753ca40f4f8ebdb9f852b722aee7
49 N94a4f7bb9a8245aa975868ab6745821e
50 schema:publisher Nb4cf5b26721f43a9a79258f9b24f587e
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107244329
52 https://doi.org/10.1007/978-3-030-00801-7_3
53 schema:sdDatePublished 2021-11-01T18:53
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N9140b375ed6f4f7eaa055148a5bac77a
56 schema:url https://doi.org/10.1007/978-3-030-00801-7_3
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N0392753ca40f4f8ebdb9f852b722aee7 schema:name dimensions_id
61 schema:value pub.1107244329
62 rdf:type schema:PropertyValue
63 N19da4e28ed8d4945982a2c6ef9d83b31 schema:familyName Abreu
64 schema:givenName Salvador
65 rdf:type schema:Person
66 N1d39e1a78ff84a02ad0b73a23e950b47 rdf:first N19da4e28ed8d4945982a2c6ef9d83b31
67 rdf:rest rdf:nil
68 N2a642dd4b4de42e6b3a07a32107c9917 schema:familyName Hanus
69 schema:givenName Michael
70 rdf:type schema:Person
71 N9140b375ed6f4f7eaa055148a5bac77a schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N923af86b05c74876a5b0b1701275c7c6 rdf:first N2a642dd4b4de42e6b3a07a32107c9917
74 rdf:rest N1d39e1a78ff84a02ad0b73a23e950b47
75 N94a4f7bb9a8245aa975868ab6745821e schema:name doi
76 schema:value 10.1007/978-3-030-00801-7_3
77 rdf:type schema:PropertyValue
78 N94dec6291a9c44328f3625d10f3b1fc7 rdf:first Ne37a977b742d40548a8b61d64493b2c8
79 rdf:rest N923af86b05c74876a5b0b1701275c7c6
80 N99131994df734e61ad5d141eb4a8a1f5 rdf:first sg:person.013750414271.15
81 rdf:rest rdf:nil
82 Nb4cf5b26721f43a9a79258f9b24f587e schema:name Springer Nature
83 rdf:type schema:Organisation
84 Ne37a977b742d40548a8b61d64493b2c8 schema:familyName Seipel
85 schema:givenName Dietmar
86 rdf:type schema:Person
87 Ne674333757444638b6f4f848006fe3a4 schema:isbn 978-3-030-00800-0
88 978-3-030-00801-7
89 schema:name Declarative Programming and Knowledge Management
90 rdf:type schema:Book
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.013750414271.15 schema:affiliation grid-institutes:grid.6582.9
98 schema:familyName Frühwirth
99 schema:givenName Thom
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
101 rdf:type schema:Person
102 grid-institutes:grid.6582.9 schema:alternateName Ulm University, Ulm, Germany
103 schema:name Ulm University, Ulm, Germany
104 rdf:type schema:Organization
 




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


...