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

References to SciGraph publications

  • 2015. Constraint Handling Rules - What Else? in RULE TECHNOLOGIES: FOUNDATIONS, TOOLS, AND APPLICATIONS
  • 2004. The Refined Operational Semantics of Constraint Handling Rules in LOGIC PROGRAMMING
  • 2004. Integration and Optimization of Rule-Based Constraint Solvers in LOGIC BASED PROGRAM SYNTHESIS AND TRANSFORMATION
  • 2001. Adaptive Constraint Handling with CHR in Java in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP 2001
  • 2018. Justifications in Constraint Handling Rules for Logical Retraction in Dynamic Algorithms in LOGIC-BASED PROGRAM SYNTHESIS AND TRANSFORMATION
  • 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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Ulm", 
              "id": "https://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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-319-21542-6_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010556081", 
              "https://doi.org/10.1007/978-3-319-21542-6_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-25938-1_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030083923", 
              "https://doi.org/10.1007/978-3-540-25938-1_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-25938-1_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030083923", 
              "https://doi.org/10.1007/978-3-540-25938-1_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27775-0_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043968221", 
              "https://doi.org/10.1007/978-3-540-27775-0_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27775-0_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043968221", 
              "https://doi.org/10.1007/978-3-540-27775-0_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/088395100117052", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048214470"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45578-7_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051810129", 
              "https://doi.org/10.1007/3-540-45578-7_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s1571-0661(04)00288-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053397622"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s1471068405002541", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053824991"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s1471068405002541", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053824991"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s1471068412000208", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054088935"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511609886", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098740870"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-94460-9_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105427502", 
              "https://doi.org/10.1007/978-3-319-94460-9_9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "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"
        }, 
        "name": "Implementation of Logical Retraction in Constraint Handling Rules with Justifications", 
        "pagination": "37-52", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-030-00801-7_3"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b4107792292eedf71222e15b642260b94bcf2ecacad9ce6c0a5cadf9625eac7a"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1107244329"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "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": "2019-04-16T04:39", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000321_0000000321/records_74936_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-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.

    110 TRIPLES      23 PREDICATES      36 URIs      19 LITERALS      8 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 N2c4014a699cb4be3ad61a21678ad36e5
    4 schema:citation sg:pub.10.1007/3-540-45578-7_18
    5 sg:pub.10.1007/978-3-319-21542-6_2
    6 sg:pub.10.1007/978-3-319-94460-9_9
    7 sg:pub.10.1007/978-3-540-25938-1_17
    8 sg:pub.10.1007/978-3-540-27775-0_7
    9 https://doi.org/10.1016/s1571-0661(04)00288-9
    10 https://doi.org/10.1017/cbo9780511609886
    11 https://doi.org/10.1017/s1471068405002541
    12 https://doi.org/10.1017/s1471068412000208
    13 https://doi.org/10.1080/088395100117052
    14 schema:datePublished 2018-09-27
    15 schema:datePublishedReg 2018-09-27
    16 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.
    17 schema:editor N6993ee246fb6440ca9b5e2f55df2f527
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N7dec0a2eeba549bcbf9162131841be5e
    22 schema:name Implementation of Logical Retraction in Constraint Handling Rules with Justifications
    23 schema:pagination 37-52
    24 schema:productId N0578a1875e274ca7a7f6bba29f2e6bc9
    25 N5967c29b67eb46c485a7e5e0ebd8ce1a
    26 Nb119c652f0b44fcaa055a2f818a0a0de
    27 schema:publisher N6c6aa0084121417eb5bc610d0d257e16
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107244329
    29 https://doi.org/10.1007/978-3-030-00801-7_3
    30 schema:sdDatePublished 2019-04-16T04:39
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher N19511e93cc8f456997445e31d3a93c8a
    33 schema:url https://link.springer.com/10.1007%2F978-3-030-00801-7_3
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset chapters
    36 rdf:type schema:Chapter
    37 N0578a1875e274ca7a7f6bba29f2e6bc9 schema:name readcube_id
    38 schema:value b4107792292eedf71222e15b642260b94bcf2ecacad9ce6c0a5cadf9625eac7a
    39 rdf:type schema:PropertyValue
    40 N0b755cd5bb084d77a3235f970e28cf39 schema:familyName Seipel
    41 schema:givenName Dietmar
    42 rdf:type schema:Person
    43 N19511e93cc8f456997445e31d3a93c8a schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N2c4014a699cb4be3ad61a21678ad36e5 rdf:first sg:person.013750414271.15
    46 rdf:rest rdf:nil
    47 N4165b6ad84fb4dd1a8d5cec1fb38a09d rdf:first Nd603a7f074004585acf1ae2319bf246b
    48 rdf:rest rdf:nil
    49 N5967c29b67eb46c485a7e5e0ebd8ce1a schema:name dimensions_id
    50 schema:value pub.1107244329
    51 rdf:type schema:PropertyValue
    52 N5f599cfb83b84fc793c41b62f57c1dcc rdf:first N697e972525d7499cb096798c3b365f68
    53 rdf:rest N4165b6ad84fb4dd1a8d5cec1fb38a09d
    54 N697e972525d7499cb096798c3b365f68 schema:familyName Hanus
    55 schema:givenName Michael
    56 rdf:type schema:Person
    57 N6993ee246fb6440ca9b5e2f55df2f527 rdf:first N0b755cd5bb084d77a3235f970e28cf39
    58 rdf:rest N5f599cfb83b84fc793c41b62f57c1dcc
    59 N6c6aa0084121417eb5bc610d0d257e16 schema:location Cham
    60 schema:name Springer International Publishing
    61 rdf:type schema:Organisation
    62 N7dec0a2eeba549bcbf9162131841be5e schema:isbn 978-3-030-00800-0
    63 978-3-030-00801-7
    64 schema:name Declarative Programming and Knowledge Management
    65 rdf:type schema:Book
    66 Nb119c652f0b44fcaa055a2f818a0a0de schema:name doi
    67 schema:value 10.1007/978-3-030-00801-7_3
    68 rdf:type schema:PropertyValue
    69 Nd603a7f074004585acf1ae2319bf246b schema:familyName Abreu
    70 schema:givenName Salvador
    71 rdf:type schema:Person
    72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Information and Computing Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Computation Theory and Mathematics
    77 rdf:type schema:DefinedTerm
    78 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
    79 schema:familyName Frühwirth
    80 schema:givenName Thom
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
    82 rdf:type schema:Person
    83 sg:pub.10.1007/3-540-45578-7_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051810129
    84 https://doi.org/10.1007/3-540-45578-7_18
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1007/978-3-319-21542-6_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010556081
    87 https://doi.org/10.1007/978-3-319-21542-6_2
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/978-3-319-94460-9_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105427502
    90 https://doi.org/10.1007/978-3-319-94460-9_9
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/978-3-540-25938-1_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030083923
    93 https://doi.org/10.1007/978-3-540-25938-1_17
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-3-540-27775-0_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043968221
    96 https://doi.org/10.1007/978-3-540-27775-0_7
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/s1571-0661(04)00288-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053397622
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1017/cbo9780511609886 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098740870
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1017/s1471068405002541 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053824991
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1017/s1471068412000208 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054088935
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1080/088395100117052 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048214470
    107 rdf:type schema:CreativeWork
    108 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
    109 schema:name Ulm University, Ulm, Germany
    110 rdf:type schema:Organization
     




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


    ...