Operational semantics and confluence of constraint propagation rules View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005-06-10

AUTHORS

Slim Abdennadher

ABSTRACT

Constraint Handling Rules (CHR) allow one to specify and implement both propagation and simplification for user-defined constraints. Since a propagation rule is applicable again and again, we present in this paper for the first time an operational semantics for CHR that avoids the termination problem with propagation rules. In previous work [AFM96], a sufficient and necessary condition for the confluence of terminating simplification rules was given inspired by results about conditional term rewriting systems. Confluence ensures that the solver will always compute the same result for a given set of constraints independent of which rules are applied. The confluence of propagation rules was an open problem. This paper shows that we can also give a sufficient and a necessary condition for confluence of terminating CHR programs with propagation rules based on the more refined operational semantics. More... »

PAGES

252-266

References to SciGraph publications

  • 1985. Contextual rewriting in REWRITING TECHNIQUES AND APPLICATIONS
  • 1995. Constraint Programming: Basics and Trends, 1994 Châtillon Spring School Châtillon-sur-Seine, France, May 16–20, 1994 Selected Papers in NONE
  • 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
  • Book

    TITLE

    Principles and Practice of Constraint Programming-CP97

    ISBN

    978-3-540-63753-0
    978-3-540-69642-1

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bfb0017444

    DOI

    http://dx.doi.org/10.1007/bfb0017444

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "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 Department, 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"
          }
        ], 
        "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": "sg:pub.10.1007/3-540-15976-2_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036331844", 
              "https://doi.org/10.1007/3-540-15976-2_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0269888900005798", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041890195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/1968867", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069674273"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-59155-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109702682", 
              "https://doi.org/10.1007/3-540-59155-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-59155-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109702682", 
              "https://doi.org/10.1007/3-540-59155-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-59155-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109702682", 
              "https://doi.org/10.1007/3-540-59155-9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005-06-10", 
        "datePublishedReg": "2005-06-10", 
        "description": "Constraint Handling Rules (CHR) allow one to specify and implement both propagation and simplification for user-defined constraints. Since a propagation rule is applicable again and again, we present in this paper for the first time an operational semantics for CHR that avoids the termination problem with propagation rules. In previous work [AFM96], a sufficient and necessary condition for the confluence of terminating simplification rules was given inspired by results about conditional term rewriting systems. Confluence ensures that the solver will always compute the same result for a given set of constraints independent of which rules are applied. The confluence of propagation rules was an open problem. This paper shows that we can also give a sufficient and a necessary condition for confluence of terminating CHR programs with propagation rules based on the more refined operational semantics.", 
        "editor": [
          {
            "familyName": "Smolka", 
            "givenName": "Gert", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/bfb0017444", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-63753-0", 
            "978-3-540-69642-1"
          ], 
          "name": "Principles and Practice of Constraint Programming-CP97", 
          "type": "Book"
        }, 
        "name": "Operational semantics and confluence of constraint propagation rules", 
        "pagination": "252-266", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1010989701"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bfb0017444"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "345c3d1ecc8fe1de52b00aab3773f89c8354a0a4e49759d2470f49a0583be3c1"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/bfb0017444", 
          "https://app.dimensions.ai/details/publication/pub.1010989701"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T09:27", 
        "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/0000000372_0000000372/records_117100_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2FBFb0017444"
      }
    ]
     

    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/bfb0017444'

    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/bfb0017444'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0017444'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0017444'


     

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

    90 TRIPLES      23 PREDICATES      33 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bfb0017444 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author Ne777316fd8674be9b5a170e6dcf3d569
    4 schema:citation sg:pub.10.1007/3-540-15976-2_2
    5 sg:pub.10.1007/3-540-19242-5_3
    6 sg:pub.10.1007/3-540-59155-9
    7 sg:pub.10.1007/3-540-61551-2_62
    8 https://doi.org/10.1016/0743-1066(94)90033-7
    9 https://doi.org/10.1017/s0269888900005798
    10 https://doi.org/10.2307/1968867
    11 schema:datePublished 2005-06-10
    12 schema:datePublishedReg 2005-06-10
    13 schema:description Constraint Handling Rules (CHR) allow one to specify and implement both propagation and simplification for user-defined constraints. Since a propagation rule is applicable again and again, we present in this paper for the first time an operational semantics for CHR that avoids the termination problem with propagation rules. In previous work [AFM96], a sufficient and necessary condition for the confluence of terminating simplification rules was given inspired by results about conditional term rewriting systems. Confluence ensures that the solver will always compute the same result for a given set of constraints independent of which rules are applied. The confluence of propagation rules was an open problem. This paper shows that we can also give a sufficient and a necessary condition for confluence of terminating CHR programs with propagation rules based on the more refined operational semantics.
    14 schema:editor N8142f113813f4b9f88e32aaad47dcd99
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N52682f509b02439c9da473a53ad0cbab
    19 schema:name Operational semantics and confluence of constraint propagation rules
    20 schema:pagination 252-266
    21 schema:productId N554372d0c21648e99c5f9b35a2c53775
    22 N62b101342e44416fbc940a32881f5abc
    23 Ncba8c1eeb26f4e91b33b54d4f6f3f9b1
    24 schema:publisher Ne026e2ca5bb2436d9e1b5c2651fa8b63
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010989701
    26 https://doi.org/10.1007/bfb0017444
    27 schema:sdDatePublished 2019-04-16T09:27
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N46007dcee8654bf182a844fac638640d
    30 schema:url https://link.springer.com/10.1007%2FBFb0017444
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N09cfce60045740f1a2a2b8ca721730a1 schema:familyName Smolka
    35 schema:givenName Gert
    36 rdf:type schema:Person
    37 N46007dcee8654bf182a844fac638640d schema:name Springer Nature - SN SciGraph project
    38 rdf:type schema:Organization
    39 N52682f509b02439c9da473a53ad0cbab schema:isbn 978-3-540-63753-0
    40 978-3-540-69642-1
    41 schema:name Principles and Practice of Constraint Programming-CP97
    42 rdf:type schema:Book
    43 N554372d0c21648e99c5f9b35a2c53775 schema:name readcube_id
    44 schema:value 345c3d1ecc8fe1de52b00aab3773f89c8354a0a4e49759d2470f49a0583be3c1
    45 rdf:type schema:PropertyValue
    46 N62b101342e44416fbc940a32881f5abc schema:name dimensions_id
    47 schema:value pub.1010989701
    48 rdf:type schema:PropertyValue
    49 N8142f113813f4b9f88e32aaad47dcd99 rdf:first N09cfce60045740f1a2a2b8ca721730a1
    50 rdf:rest rdf:nil
    51 Ncba8c1eeb26f4e91b33b54d4f6f3f9b1 schema:name doi
    52 schema:value 10.1007/bfb0017444
    53 rdf:type schema:PropertyValue
    54 Ne026e2ca5bb2436d9e1b5c2651fa8b63 schema:location Berlin, Heidelberg
    55 schema:name Springer Berlin Heidelberg
    56 rdf:type schema:Organisation
    57 Ne777316fd8674be9b5a170e6dcf3d569 rdf:first sg:person.010445445574.13
    58 rdf:rest rdf:nil
    59 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Information and Computing Sciences
    61 rdf:type schema:DefinedTerm
    62 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information Systems
    64 rdf:type schema:DefinedTerm
    65 sg:person.010445445574.13 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
    66 schema:familyName Abdennadher
    67 schema:givenName Slim
    68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
    69 rdf:type schema:Person
    70 sg:pub.10.1007/3-540-15976-2_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036331844
    71 https://doi.org/10.1007/3-540-15976-2_2
    72 rdf:type schema:CreativeWork
    73 sg:pub.10.1007/3-540-19242-5_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016280037
    74 https://doi.org/10.1007/3-540-19242-5_3
    75 rdf:type schema:CreativeWork
    76 sg:pub.10.1007/3-540-59155-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109702682
    77 https://doi.org/10.1007/3-540-59155-9
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/3-540-61551-2_62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024772408
    80 https://doi.org/10.1007/3-540-61551-2_62
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1016/0743-1066(94)90033-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004885944
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1017/s0269888900005798 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041890195
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.2307/1968867 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069674273
    87 rdf:type schema:CreativeWork
    88 https://www.grid.ac/institutes/grid.5252.0 schema:alternateName Ludwig Maximilian University of Munich
    89 schema:name Computer Science Department, University of Munich, Oettingenstr. 67, 80538, München, Germany
    90 rdf:type schema:Organization
     




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


    ...