On Completion of Constraint Handling Rules View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999-06-11

AUTHORS

Slim Abdennadher , Thom Frühwirth

ABSTRACT

Constraint Handling Rules (CHR) is a high-level language for writing constraint solvers either from scratch or by modifying existing solvers. An important property of any constraint solver is confluence: The result of a computation should be independent from the order in which constraints arrive and in which rules are applied. In previous work [1], a sufficient and necessary condition for the confluence of terminating CHR programs was given by adapting and extending results about conditional term rewriting systems. In this paper we investigate so-called completion methods that make a non-confluent CHR program confluent by adding new rules. As it turns out, completion can also exhibit inconsistency of a CHR program. Moreover, as shown in this paper, completion can be used to define new constraints in terms of already existing constraints and to derive constraint solvers for them. More... »

PAGES

25-39

References to SciGraph publications

  • 2007. Reliable Software Technologies – Ada Europe 2007, 12th Ada-Europe International Conference on Reliable Software Technologies, Geneva, Switzerland, June 25-29, 2007. Proceedings in NONE
  • 1986. Commutation, transformation, and termination in 8TH INTERNATIONAL CONFERENCE ON AUTOMATED DEDUCTION
  • 1988. Confluence of conditional rewrite systems in CONDITIONAL TERM REWRITING SYSTEMS
  • 1996. On confluence of Constraint Handling Rules in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP96
  • 1995. Constraint handling rules in CONSTRAINT PROGRAMMING: BASICS AND TRENDS
  • Book

    TITLE

    Principles and Practice of Constraint Programming — CP98

    ISBN

    978-3-540-65224-3
    978-3-540-49481-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-49481-2_4

    DOI

    http://dx.doi.org/10.1007/3-540-49481-2_4

    DIMENSIONS

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


    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/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "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": "Ludwig Maximilian University of Munich", 
              "id": "https://www.grid.ac/institutes/grid.5252.0", 
              "name": [
                "Computer Science Institute, University of Munich Oettingenstr, 67, 80538, M\u00fcnchen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Abdennadher", 
            "givenName": "Slim", 
            "id": "sg:person.010445445574.13", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Ludwig Maximilian University of Munich", 
              "id": "https://www.grid.ac/institutes/grid.5252.0", 
              "name": [
                "Computer Science Institute, University of Munich Oettingenstr, 67, 80538, M\u00fcnchen, 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": "https://doi.org/10.1016/0743-1066(94)90033-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004885944"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-19242-5_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016280037", 
              "https://doi.org/10.1007/3-540-19242-5_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61551-2_62", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024772408", 
              "https://doi.org/10.1007/3-540-61551-2_62"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0743-1066(92)90050-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030062350"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73230-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031528167", 
              "https://doi.org/10.1007/978-3-540-73230-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73230-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031528167", 
              "https://doi.org/10.1007/978-3-540-73230-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-59155-9_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039095944", 
              "https://doi.org/10.1007/3-540-59155-9_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-16780-3_76", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052126523", 
              "https://doi.org/10.1007/3-540-16780-3_76"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1110622512", 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1999-06-11", 
        "datePublishedReg": "1999-06-11", 
        "description": "Constraint Handling Rules (CHR) is a high-level language for writing constraint solvers either from scratch or by modifying existing solvers. An important property of any constraint solver is confluence: The result of a computation should be independent from the order in which constraints arrive and in which rules are applied. In previous work [1], a sufficient and necessary condition for the confluence of terminating CHR programs was given by adapting and extending results about conditional term rewriting systems. In this paper we investigate so-called completion methods that make a non-confluent CHR program confluent by adding new rules. As it turns out, completion can also exhibit inconsistency of a CHR program. Moreover, as shown in this paper, completion can be used to define new constraints in terms of already existing constraints and to derive constraint solvers for them.", 
        "editor": [
          {
            "familyName": "Maher", 
            "givenName": "Michael", 
            "type": "Person"
          }, 
          {
            "familyName": "Puget", 
            "givenName": "Jean-Francois", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-49481-2_4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-65224-3", 
            "978-3-540-49481-2"
          ], 
          "name": "Principles and Practice of Constraint Programming \u2014 CP98", 
          "type": "Book"
        }, 
        "name": "On Completion of Constraint Handling Rules", 
        "pagination": "25-39", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-49481-2_4"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "ffac5da22caae1dc88aebc9fd71d290a3e0249ed784ae098423f38f1be44f287"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1053677545"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-49481-2_4", 
          "https://app.dimensions.ai/details/publication/pub.1053677545"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:48", 
        "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/0000000347_0000000347/records_89819_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-49481-2_4"
      }
    ]
     

    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/3-540-49481-2_4'

    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/3-540-49481-2_4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49481-2_4'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-49481-2_4'


     

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

    105 TRIPLES      23 PREDICATES      34 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-49481-2_4 schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author Na66cf616424a4a9a87d395439d60cdce
    4 schema:citation sg:pub.10.1007/3-540-16780-3_76
    5 sg:pub.10.1007/3-540-19242-5_3
    6 sg:pub.10.1007/3-540-59155-9_6
    7 sg:pub.10.1007/3-540-61551-2_62
    8 sg:pub.10.1007/978-3-540-73230-3
    9 https://app.dimensions.ai/details/publication/pub.1110622512
    10 https://doi.org/10.1016/0743-1066(92)90050-d
    11 https://doi.org/10.1016/0743-1066(94)90033-7
    12 schema:datePublished 1999-06-11
    13 schema:datePublishedReg 1999-06-11
    14 schema:description Constraint Handling Rules (CHR) is a high-level language for writing constraint solvers either from scratch or by modifying existing solvers. An important property of any constraint solver is confluence: The result of a computation should be independent from the order in which constraints arrive and in which rules are applied. In previous work [1], a sufficient and necessary condition for the confluence of terminating CHR programs was given by adapting and extending results about conditional term rewriting systems. In this paper we investigate so-called completion methods that make a non-confluent CHR program confluent by adding new rules. As it turns out, completion can also exhibit inconsistency of a CHR program. Moreover, as shown in this paper, completion can be used to define new constraints in terms of already existing constraints and to derive constraint solvers for them.
    15 schema:editor N47c21756e4db497785613d776bf97f88
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf Nf5cc475ec33f413e9feb029532a7797a
    20 schema:name On Completion of Constraint Handling Rules
    21 schema:pagination 25-39
    22 schema:productId N2927daad26a740b5878d7ff28afa9b20
    23 Na6c65ac5adc64779bf67d3b683a37135
    24 Nc20da960db08441fa2b21484a2c6a14f
    25 schema:publisher N15d531240b8c4a12b3c74419c440db82
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053677545
    27 https://doi.org/10.1007/3-540-49481-2_4
    28 schema:sdDatePublished 2019-04-16T05:48
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher Nf915f7b631b74d38a30b821a541b23ee
    31 schema:url https://link.springer.com/10.1007%2F3-540-49481-2_4
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N15d531240b8c4a12b3c74419c440db82 schema:location Berlin, Heidelberg
    36 schema:name Springer Berlin Heidelberg
    37 rdf:type schema:Organisation
    38 N2927daad26a740b5878d7ff28afa9b20 schema:name dimensions_id
    39 schema:value pub.1053677545
    40 rdf:type schema:PropertyValue
    41 N47c21756e4db497785613d776bf97f88 rdf:first N64e4c3f24bad4a6fbcb199dbb3947b4f
    42 rdf:rest N52dd3757168d416ca0be3eb02d489148
    43 N52dd3757168d416ca0be3eb02d489148 rdf:first Nd0fe1eceeee244949c8973a1500c2599
    44 rdf:rest rdf:nil
    45 N64e4c3f24bad4a6fbcb199dbb3947b4f schema:familyName Maher
    46 schema:givenName Michael
    47 rdf:type schema:Person
    48 N6979fb5431b249d99f4ab3ec355a82cf rdf:first sg:person.013750414271.15
    49 rdf:rest rdf:nil
    50 Na66cf616424a4a9a87d395439d60cdce rdf:first sg:person.010445445574.13
    51 rdf:rest N6979fb5431b249d99f4ab3ec355a82cf
    52 Na6c65ac5adc64779bf67d3b683a37135 schema:name doi
    53 schema:value 10.1007/3-540-49481-2_4
    54 rdf:type schema:PropertyValue
    55 Nc20da960db08441fa2b21484a2c6a14f schema:name readcube_id
    56 schema:value ffac5da22caae1dc88aebc9fd71d290a3e0249ed784ae098423f38f1be44f287
    57 rdf:type schema:PropertyValue
    58 Nd0fe1eceeee244949c8973a1500c2599 schema:familyName Puget
    59 schema:givenName Jean-Francois
    60 rdf:type schema:Person
    61 Nf5cc475ec33f413e9feb029532a7797a schema:isbn 978-3-540-49481-2
    62 978-3-540-65224-3
    63 schema:name Principles and Practice of Constraint Programming — CP98
    64 rdf:type schema:Book
    65 Nf915f7b631b74d38a30b821a541b23ee schema:name Springer Nature - SN SciGraph project
    66 rdf:type schema:Organization
    67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Information and Computing Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Computer Software
    72 rdf:type schema:DefinedTerm
    73 sg:person.010445445574.13 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
    74 schema:familyName Abdennadher
    75 schema:givenName Slim
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
    77 rdf:type schema:Person
    78 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
    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-16780-3_76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052126523
    84 https://doi.org/10.1007/3-540-16780-3_76
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1007/3-540-19242-5_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016280037
    87 https://doi.org/10.1007/3-540-19242-5_3
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/3-540-59155-9_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039095944
    90 https://doi.org/10.1007/3-540-59155-9_6
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/3-540-61551-2_62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024772408
    93 https://doi.org/10.1007/3-540-61551-2_62
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-3-540-73230-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031528167
    96 https://doi.org/10.1007/978-3-540-73230-3
    97 rdf:type schema:CreativeWork
    98 https://app.dimensions.ai/details/publication/pub.1110622512 schema:CreativeWork
    99 https://doi.org/10.1016/0743-1066(92)90050-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1030062350
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0743-1066(94)90033-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004885944
    102 rdf:type schema:CreativeWork
    103 https://www.grid.ac/institutes/grid.5252.0 schema:alternateName Ludwig Maximilian University of Munich
    104 schema:name Computer Science Institute, University of Munich Oettingenstr, 67, 80538, München, Germany
    105 rdf:type schema:Organization
     




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


    ...