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 N34bebf5fb45045448dea7b8ad539d154
    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 Nce1666c1e2344545892bddcd494f815d
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N2625101aba3d4e999eb6a567eef33a7e
    19 schema:name Operational semantics and confluence of constraint propagation rules
    20 schema:pagination 252-266
    21 schema:productId N08387a1dfd014adbaeed3e392701ae14
    22 Nbbd92cd7889440a7bc868f82c5d73d47
    23 Nc902d3a0e8bb43d2b7a0be1cacff4375
    24 schema:publisher N5082cf20f8d7435a9af0193e0163d4dc
    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 N04ac44ea08e748b4a58d83117ce84ed8
    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 N04ac44ea08e748b4a58d83117ce84ed8 schema:name Springer Nature - SN SciGraph project
    35 rdf:type schema:Organization
    36 N08387a1dfd014adbaeed3e392701ae14 schema:name doi
    37 schema:value 10.1007/bfb0017444
    38 rdf:type schema:PropertyValue
    39 N1db8d86a54ad4cd5a9e718d89ad943d1 schema:familyName Smolka
    40 schema:givenName Gert
    41 rdf:type schema:Person
    42 N2625101aba3d4e999eb6a567eef33a7e schema:isbn 978-3-540-63753-0
    43 978-3-540-69642-1
    44 schema:name Principles and Practice of Constraint Programming-CP97
    45 rdf:type schema:Book
    46 N34bebf5fb45045448dea7b8ad539d154 rdf:first sg:person.010445445574.13
    47 rdf:rest rdf:nil
    48 N5082cf20f8d7435a9af0193e0163d4dc schema:location Berlin, Heidelberg
    49 schema:name Springer Berlin Heidelberg
    50 rdf:type schema:Organisation
    51 Nbbd92cd7889440a7bc868f82c5d73d47 schema:name dimensions_id
    52 schema:value pub.1010989701
    53 rdf:type schema:PropertyValue
    54 Nc902d3a0e8bb43d2b7a0be1cacff4375 schema:name readcube_id
    55 schema:value 345c3d1ecc8fe1de52b00aab3773f89c8354a0a4e49759d2470f49a0583be3c1
    56 rdf:type schema:PropertyValue
    57 Nce1666c1e2344545892bddcd494f815d rdf:first N1db8d86a54ad4cd5a9e718d89ad943d1
    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)


    ...