On confluence of Constraint Handling Rules View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1996

AUTHORS

Slim Abdennadher , Thom Frühwirth , Holger Meuss

ABSTRACT

We introduce the notion of confluence for Constraint Handling Rules (CHR), a powerful language for writing constraint solvers. With CHR one simplifies and solves constraints by applying rules. Confluence guarantees that a CHR program will always compute the same result for a given set of constraints independent of which rules are applied. We give a decidable, sufficient and necessary syntactic condition for confluence. Confluence turns out to be an essential syntactical property of CHR programs for two reasons. First, confluence implies correctness (as will be shown in this paper). In a correct CHR program, application of CHR rules preserves logical equivalence of the simplified constraints. Secondly, even when the program is already correct, confluence is highly desirable. Otherwise, given some constraints, one computation may detect their inconsistency while another one may just simplify them into a still complex constraint. As a side-effect, the paper also gives soundness and completeness results for CHR programs. Due to their special nature, and in particular correctness, these theorems are stronger than what holds for the related families of (concurrent) constraint programming languages. More... »

PAGES

1-15

Book

TITLE

Principles and Practice of Constraint Programming — CP96

ISBN

978-3-540-61551-4
978-3-540-70620-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-61551-2_62

DOI

http://dx.doi.org/10.1007/3-540-61551-2_62

DIMENSIONS

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


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 Department, University of Munich, Oettingenstr. 67, 80538\u00a0Munich, 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 Department, University of Munich, Oettingenstr. 67, 80538\u00a0Munich, 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"
      }, 
      {
        "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\u00a0Munich, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Meuss", 
        "givenName": "Holger", 
        "id": "sg:person.016641077043.80", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641077043.80"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "We introduce the notion of confluence for Constraint Handling Rules (CHR), a powerful language for writing constraint solvers. With CHR one simplifies and solves constraints by applying rules. Confluence guarantees that a CHR program will always compute the same result for a given set of constraints independent of which rules are applied. We give a decidable, sufficient and necessary syntactic condition for confluence. Confluence turns out to be an essential syntactical property of CHR programs for two reasons. First, confluence implies correctness (as will be shown in this paper). In a correct CHR program, application of CHR rules preserves logical equivalence of the simplified constraints. Secondly, even when the program is already correct, confluence is highly desirable. Otherwise, given some constraints, one computation may detect their inconsistency while another one may just simplify them into a still complex constraint. As a side-effect, the paper also gives soundness and completeness results for CHR programs. Due to their special nature, and in particular correctness, these theorems are stronger than what holds for the related families of (concurrent) constraint programming languages.", 
    "editor": [
      {
        "familyName": "Freuder", 
        "givenName": "Eugene C.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-61551-2_62", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-61551-4", 
        "978-3-540-70620-5"
      ], 
      "name": "Principles and Practice of Constraint Programming \u2014 CP96", 
      "type": "Book"
    }, 
    "name": "On confluence of Constraint Handling Rules", 
    "pagination": "1-15", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-61551-2_62"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "7604377748a8dcb115c31ac16b23fed12f20a93393f21c3683cde347064eae79"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024772408"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-61551-2_62", 
      "https://app.dimensions.ai/details/publication/pub.1024772408"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11:18", 
    "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/0000000001_0000000264/records_8660_00000042.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-61551-2_62"
  }
]
 

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-61551-2_62'

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-61551-2_62'

Turtle is a human-readable linked data format.

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

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-61551-2_62'


 

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

79 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-61551-2_62 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N438f8e3d5b034dea937fcc37f875386a
4 schema:datePublished 1996
5 schema:datePublishedReg 1996-01-01
6 schema:description We introduce the notion of confluence for Constraint Handling Rules (CHR), a powerful language for writing constraint solvers. With CHR one simplifies and solves constraints by applying rules. Confluence guarantees that a CHR program will always compute the same result for a given set of constraints independent of which rules are applied. We give a decidable, sufficient and necessary syntactic condition for confluence. Confluence turns out to be an essential syntactical property of CHR programs for two reasons. First, confluence implies correctness (as will be shown in this paper). In a correct CHR program, application of CHR rules preserves logical equivalence of the simplified constraints. Secondly, even when the program is already correct, confluence is highly desirable. Otherwise, given some constraints, one computation may detect their inconsistency while another one may just simplify them into a still complex constraint. As a side-effect, the paper also gives soundness and completeness results for CHR programs. Due to their special nature, and in particular correctness, these theorems are stronger than what holds for the related families of (concurrent) constraint programming languages.
7 schema:editor N60773a28ce9f44259f2605dc4f50f161
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N8b98b8885a554ed5a33c1b284c9497e5
12 schema:name On confluence of Constraint Handling Rules
13 schema:pagination 1-15
14 schema:productId N3ac973d764dc44d0986553bbcfde2177
15 N4ddab155daa24d3ba6712416213b55e4
16 N7539b7684f694999a704e26196199f1f
17 schema:publisher Nf15623d0bd1f46398bd5af614b616d89
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024772408
19 https://doi.org/10.1007/3-540-61551-2_62
20 schema:sdDatePublished 2019-04-15T11:18
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N00f5f337e62e42d5a051b4eb63495264
23 schema:url http://link.springer.com/10.1007/3-540-61551-2_62
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N00f5f337e62e42d5a051b4eb63495264 schema:name Springer Nature - SN SciGraph project
28 rdf:type schema:Organization
29 N3ac973d764dc44d0986553bbcfde2177 schema:name dimensions_id
30 schema:value pub.1024772408
31 rdf:type schema:PropertyValue
32 N438f8e3d5b034dea937fcc37f875386a rdf:first sg:person.010445445574.13
33 rdf:rest N8ed346ab48664765a6ada7b1f271d7a7
34 N4ddab155daa24d3ba6712416213b55e4 schema:name readcube_id
35 schema:value 7604377748a8dcb115c31ac16b23fed12f20a93393f21c3683cde347064eae79
36 rdf:type schema:PropertyValue
37 N60773a28ce9f44259f2605dc4f50f161 rdf:first Naccd7fe6a1a94676a53e2a8019c4f7eb
38 rdf:rest rdf:nil
39 N7539b7684f694999a704e26196199f1f schema:name doi
40 schema:value 10.1007/3-540-61551-2_62
41 rdf:type schema:PropertyValue
42 N8b98b8885a554ed5a33c1b284c9497e5 schema:isbn 978-3-540-61551-4
43 978-3-540-70620-5
44 schema:name Principles and Practice of Constraint Programming — CP96
45 rdf:type schema:Book
46 N8ed346ab48664765a6ada7b1f271d7a7 rdf:first sg:person.013750414271.15
47 rdf:rest Nc0bcc4f4a2ed4a34b431408e49a3b444
48 Naccd7fe6a1a94676a53e2a8019c4f7eb schema:familyName Freuder
49 schema:givenName Eugene C.
50 rdf:type schema:Person
51 Nc0bcc4f4a2ed4a34b431408e49a3b444 rdf:first sg:person.016641077043.80
52 rdf:rest rdf:nil
53 Nf15623d0bd1f46398bd5af614b616d89 schema:location Berlin, Heidelberg
54 schema:name Springer Berlin Heidelberg
55 rdf:type schema:Organisation
56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
57 schema:name Information and Computing Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
60 schema:name Computer Software
61 rdf:type schema:DefinedTerm
62 sg:person.010445445574.13 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
63 schema:familyName Abdennadher
64 schema:givenName Slim
65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
66 rdf:type schema:Person
67 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
68 schema:familyName Frühwirth
69 schema:givenName Thom
70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
71 rdf:type schema:Person
72 sg:person.016641077043.80 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
73 schema:familyName Meuss
74 schema:givenName Holger
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641077043.80
76 rdf:type schema:Person
77 https://www.grid.ac/institutes/grid.5252.0 schema:alternateName Ludwig Maximilian University of Munich
78 schema:name Computer Science Department, University of Munich, Oettingenstr. 67, 80538 Munich, Germany
79 rdf:type schema:Organization
 




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


...