On confluence of Constraint Handling Rules View Full Text


Ontology type: schema:Chapter     


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5252.0", 
          "name": [
            "Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, 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": "Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5252.0", 
          "name": [
            "Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, 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": "Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5252.0", 
          "name": [
            "Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, 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": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-61551-4", 
        "978-3-540-70620-5"
      ], 
      "name": "Principles and Practice of Constraint Programming \u2014 CP96", 
      "type": "Book"
    }, 
    "keywords": [
      "Constraint Handling Rules", 
      "CHR programs", 
      "Handling Rules", 
      "constraint programming language", 
      "set of constraints", 
      "programming language", 
      "constraint solver", 
      "CHR rules", 
      "necessary syntactic condition", 
      "complex constraints", 
      "powerful language", 
      "syntactic conditions", 
      "notion of confluence", 
      "correctness", 
      "completeness results", 
      "constraints", 
      "logical equivalence", 
      "language", 
      "rules", 
      "syntactical properties", 
      "special nature", 
      "computation", 
      "solver", 
      "soundness", 
      "simplifies", 
      "set", 
      "applications", 
      "program", 
      "inconsistencies", 
      "results", 
      "notion", 
      "same results", 
      "one", 
      "equivalence", 
      "theorem", 
      "reasons", 
      "confluence", 
      "nature", 
      "related families", 
      "properties", 
      "conditions", 
      "family", 
      "paper", 
      "CHR one simplifies", 
      "one simplifies", 
      "essential syntactical property", 
      "correct CHR program", 
      "particular correctness"
    ], 
    "name": "On confluence of Constraint Handling Rules", 
    "pagination": "1-15", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024772408"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-61551-2_62"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-61551-2_62", 
      "https://app.dimensions.ai/details/publication/pub.1024772408"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:56", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_131.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/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.

122 TRIPLES      23 PREDICATES      74 URIs      67 LITERALS      7 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 N142dc63d0b4347bfa699ca4a82388bc2
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 N7e346758d50f4f339cddd0a7560e6786
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nfd4e2e3ceb544258ba49add731e7e640
12 schema:keywords CHR one simplifies
13 CHR programs
14 CHR rules
15 Constraint Handling Rules
16 Handling Rules
17 applications
18 completeness results
19 complex constraints
20 computation
21 conditions
22 confluence
23 constraint programming language
24 constraint solver
25 constraints
26 correct CHR program
27 correctness
28 equivalence
29 essential syntactical property
30 family
31 inconsistencies
32 language
33 logical equivalence
34 nature
35 necessary syntactic condition
36 notion
37 notion of confluence
38 one
39 one simplifies
40 paper
41 particular correctness
42 powerful language
43 program
44 programming language
45 properties
46 reasons
47 related families
48 results
49 rules
50 same results
51 set
52 set of constraints
53 simplifies
54 solver
55 soundness
56 special nature
57 syntactic conditions
58 syntactical properties
59 theorem
60 schema:name On confluence of Constraint Handling Rules
61 schema:pagination 1-15
62 schema:productId Na4ce4f8a95b640be85646ca4096b24f9
63 Ne86b409e240d4534b70c54eb31f69b74
64 schema:publisher Ndbb922e1f18a42e4b49e4189f713eec9
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024772408
66 https://doi.org/10.1007/3-540-61551-2_62
67 schema:sdDatePublished 2021-12-01T19:56
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N6fe143f0101d449984979101ec9bfe59
70 schema:url https://doi.org/10.1007/3-540-61551-2_62
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N142dc63d0b4347bfa699ca4a82388bc2 rdf:first sg:person.010445445574.13
75 rdf:rest Na4a9033eff7a4c5fb0c232d6e3ad8ec2
76 N3229672fedf6450db792677889a3fc4a rdf:first sg:person.016641077043.80
77 rdf:rest rdf:nil
78 N6fe143f0101d449984979101ec9bfe59 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N7b66cf0b0f5c489a9fd2e45bc292eb54 schema:familyName Freuder
81 schema:givenName Eugene C.
82 rdf:type schema:Person
83 N7e346758d50f4f339cddd0a7560e6786 rdf:first N7b66cf0b0f5c489a9fd2e45bc292eb54
84 rdf:rest rdf:nil
85 Na4a9033eff7a4c5fb0c232d6e3ad8ec2 rdf:first sg:person.013750414271.15
86 rdf:rest N3229672fedf6450db792677889a3fc4a
87 Na4ce4f8a95b640be85646ca4096b24f9 schema:name dimensions_id
88 schema:value pub.1024772408
89 rdf:type schema:PropertyValue
90 Ndbb922e1f18a42e4b49e4189f713eec9 schema:name Springer Nature
91 rdf:type schema:Organisation
92 Ne86b409e240d4534b70c54eb31f69b74 schema:name doi
93 schema:value 10.1007/3-540-61551-2_62
94 rdf:type schema:PropertyValue
95 Nfd4e2e3ceb544258ba49add731e7e640 schema:isbn 978-3-540-61551-4
96 978-3-540-70620-5
97 schema:name Principles and Practice of Constraint Programming — CP96
98 rdf:type schema:Book
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computer Software
104 rdf:type schema:DefinedTerm
105 sg:person.010445445574.13 schema:affiliation grid-institutes:grid.5252.0
106 schema:familyName Abdennadher
107 schema:givenName Slim
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
109 rdf:type schema:Person
110 sg:person.013750414271.15 schema:affiliation grid-institutes:grid.5252.0
111 schema:familyName Frühwirth
112 schema:givenName Thom
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
114 rdf:type schema:Person
115 sg:person.016641077043.80 schema:affiliation grid-institutes:grid.5252.0
116 schema:familyName Meuss
117 schema:givenName Holger
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016641077043.80
119 rdf:type schema:Person
120 grid-institutes:grid.5252.0 schema:alternateName Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, Germany
121 schema:name Computer Science Department, University of Munich, Oettingenstr. 67, 80538, Munich, Germany
122 rdf:type schema:Organization
 




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


...