Integration and Optimization of Rule-Based Constraint Solvers View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Slim Abdennadher , Thom Frühwirth

ABSTRACT

One lesson learned from practical constraint solving applications is that constraints are often heterogeneous. Solving such constraints requires a collaboration of constraint solvers. In this paper, we introduce a methodology for the tight integration of CHR constraint programs into one such program. CHR is a high-level rule-based language for writing constraint solvers and reasoning systems. A constraint solver is well-behaved if it is terminating and confluent. When merging constraint solvers, this property may be lost. Based on previous results on CHR program analysis and transformation we show how to utilize completion to regain well-behavedness. We identify a class of solvers whose union is always confluent and we show that for preserving termination such a class is hard to find. The merged and completed constraint solvers may contain redundant rules. Utilizing the notion of operational equivalence, which is decidable for well-behaved CHR programs, we present a method to detect redundant rules in a CHR program. More... »

PAGES

198-213

Book

TITLE

Logic Based Program Synthesis and Transformation

ISBN

978-3-540-22174-6
978-3-540-25938-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-25938-1_17

DOI

http://dx.doi.org/10.1007/978-3-540-25938-1_17

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": "German University in Cairo", 
          "id": "https://www.grid.ac/institutes/grid.187323.c", 
          "name": [
            "Faculty of Information Engineering and Technology, German University Cairo, Egypt"
          ], 
          "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": "University of Ulm", 
          "id": "https://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Computer Science Faculty, University of Ulm, 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/s0743-1066(98)10005-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000275719"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0017444", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010989701", 
          "https://doi.org/10.1007/bfb0017444"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0017444", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010989701", 
          "https://doi.org/10.1007/bfb0017444"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45406-3_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014805064", 
          "https://doi.org/10.1007/3-540-45406-3_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1023426236", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-05138-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023426236", 
          "https://doi.org/10.1007/978-3-662-05138-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-05138-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023426236", 
          "https://doi.org/10.1007/978-3-662-05138-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(96)00042-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028523527"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44957-4_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031909462", 
          "https://doi.org/10.1007/3-540-44957-4_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(01)00332-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031930886"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(01)00332-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031930886"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jsco.1995.1036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037014399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44654-0_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043896941", 
          "https://doi.org/10.1007/3-540-44654-0_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-48085-3_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050960545", 
          "https://doi.org/10.1007/978-3-540-48085-3_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-48085-3_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050960545", 
          "https://doi.org/10.1007/978-3-540-48085-3_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jsco.2002.0541", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051189609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-44990-6_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053292009", 
          "https://doi.org/10.1007/3-540-44990-6_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49481-2_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053677545", 
          "https://doi.org/10.1007/3-540-49481-2_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49481-2_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053677545", 
          "https://doi.org/10.1007/3-540-49481-2_4"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "One lesson learned from practical constraint solving applications is that constraints are often heterogeneous. Solving such constraints requires a collaboration of constraint solvers. In this paper, we introduce a methodology for the tight integration of CHR constraint programs into one such program. CHR is a high-level rule-based language for writing constraint solvers and reasoning systems. A constraint solver is well-behaved if it is terminating and confluent. When merging constraint solvers, this property may be lost. Based on previous results on CHR program analysis and transformation we show how to utilize completion to regain well-behavedness. We identify a class of solvers whose union is always confluent and we show that for preserving termination such a class is hard to find. The merged and completed constraint solvers may contain redundant rules. Utilizing the notion of operational equivalence, which is decidable for well-behaved CHR programs, we present a method to detect redundant rules in a CHR program.", 
    "editor": [
      {
        "familyName": "Bruynooghe", 
        "givenName": "Maurice", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-25938-1_17", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-22174-6", 
        "978-3-540-25938-1"
      ], 
      "name": "Logic Based Program Synthesis and Transformation", 
      "type": "Book"
    }, 
    "name": "Integration and Optimization of Rule-Based Constraint Solvers", 
    "pagination": "198-213", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030083923"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-25938-1_17"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "8f5131af1fd2dce4248d6ad2a7abee9a0374aa5517e596d6ec7cbc8277c39d24"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-25938-1_17", 
      "https://app.dimensions.ai/details/publication/pub.1030083923"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:08", 
    "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/0000000360_0000000360/records_118321_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-25938-1_17"
  }
]
 

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/978-3-540-25938-1_17'

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/978-3-540-25938-1_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-25938-1_17'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-25938-1_17'


 

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

124 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-25938-1_17 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nfc5515d65caa4c24b0035a50de11be31
4 schema:citation sg:pub.10.1007/3-540-44654-0_15
5 sg:pub.10.1007/3-540-44957-4_23
6 sg:pub.10.1007/3-540-44990-6_11
7 sg:pub.10.1007/3-540-45406-3_3
8 sg:pub.10.1007/3-540-49481-2_4
9 sg:pub.10.1007/978-3-540-48085-3_4
10 sg:pub.10.1007/978-3-662-05138-2
11 sg:pub.10.1007/bfb0017444
12 https://app.dimensions.ai/details/publication/pub.1023426236
13 https://doi.org/10.1006/jsco.1995.1036
14 https://doi.org/10.1006/jsco.2002.0541
15 https://doi.org/10.1016/0304-3975(96)00042-4
16 https://doi.org/10.1016/s0304-3975(01)00332-2
17 https://doi.org/10.1016/s0743-1066(98)10005-5
18 schema:datePublished 2004
19 schema:datePublishedReg 2004-01-01
20 schema:description One lesson learned from practical constraint solving applications is that constraints are often heterogeneous. Solving such constraints requires a collaboration of constraint solvers. In this paper, we introduce a methodology for the tight integration of CHR constraint programs into one such program. CHR is a high-level rule-based language for writing constraint solvers and reasoning systems. A constraint solver is well-behaved if it is terminating and confluent. When merging constraint solvers, this property may be lost. Based on previous results on CHR program analysis and transformation we show how to utilize completion to regain well-behavedness. We identify a class of solvers whose union is always confluent and we show that for preserving termination such a class is hard to find. The merged and completed constraint solvers may contain redundant rules. Utilizing the notion of operational equivalence, which is decidable for well-behaved CHR programs, we present a method to detect redundant rules in a CHR program.
21 schema:editor Nacbce226c1084ed2bb159b01561a0888
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N2e0170ae16b745a2ae637e50a3a32dfb
26 schema:name Integration and Optimization of Rule-Based Constraint Solvers
27 schema:pagination 198-213
28 schema:productId N42a6f06db6d844889666fc42be4e79ff
29 N75be15037b55436f998f644af658cd6e
30 Necf1cdeb4cf24bc0b264e5d4f0b10bd6
31 schema:publisher N79bd1e8b1daa48b9bb01ddf90e6bcfa8
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030083923
33 https://doi.org/10.1007/978-3-540-25938-1_17
34 schema:sdDatePublished 2019-04-16T08:08
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N32f68ce6831a4f51bcfa50cb9990e9a7
37 schema:url https://link.springer.com/10.1007%2F978-3-540-25938-1_17
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N15c26bf3274d4e6a917086b2ddedf54c schema:familyName Bruynooghe
42 schema:givenName Maurice
43 rdf:type schema:Person
44 N2e0170ae16b745a2ae637e50a3a32dfb schema:isbn 978-3-540-22174-6
45 978-3-540-25938-1
46 schema:name Logic Based Program Synthesis and Transformation
47 rdf:type schema:Book
48 N32f68ce6831a4f51bcfa50cb9990e9a7 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N42a6f06db6d844889666fc42be4e79ff schema:name dimensions_id
51 schema:value pub.1030083923
52 rdf:type schema:PropertyValue
53 N6ebcbfb23ade4592b4d64b80589f124b rdf:first sg:person.013750414271.15
54 rdf:rest rdf:nil
55 N75be15037b55436f998f644af658cd6e schema:name readcube_id
56 schema:value 8f5131af1fd2dce4248d6ad2a7abee9a0374aa5517e596d6ec7cbc8277c39d24
57 rdf:type schema:PropertyValue
58 N79bd1e8b1daa48b9bb01ddf90e6bcfa8 schema:location Berlin, Heidelberg
59 schema:name Springer Berlin Heidelberg
60 rdf:type schema:Organisation
61 Nacbce226c1084ed2bb159b01561a0888 rdf:first N15c26bf3274d4e6a917086b2ddedf54c
62 rdf:rest rdf:nil
63 Necf1cdeb4cf24bc0b264e5d4f0b10bd6 schema:name doi
64 schema:value 10.1007/978-3-540-25938-1_17
65 rdf:type schema:PropertyValue
66 Nfc5515d65caa4c24b0035a50de11be31 rdf:first sg:person.010445445574.13
67 rdf:rest N6ebcbfb23ade4592b4d64b80589f124b
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
72 schema:name Artificial Intelligence and Image Processing
73 rdf:type schema:DefinedTerm
74 sg:person.010445445574.13 schema:affiliation https://www.grid.ac/institutes/grid.187323.c
75 schema:familyName Abdennadher
76 schema:givenName Slim
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
78 rdf:type schema:Person
79 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
80 schema:familyName Frühwirth
81 schema:givenName Thom
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
83 rdf:type schema:Person
84 sg:pub.10.1007/3-540-44654-0_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043896941
85 https://doi.org/10.1007/3-540-44654-0_15
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/3-540-44957-4_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031909462
88 https://doi.org/10.1007/3-540-44957-4_23
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/3-540-44990-6_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053292009
91 https://doi.org/10.1007/3-540-44990-6_11
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/3-540-45406-3_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014805064
94 https://doi.org/10.1007/3-540-45406-3_3
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/3-540-49481-2_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053677545
97 https://doi.org/10.1007/3-540-49481-2_4
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/978-3-540-48085-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050960545
100 https://doi.org/10.1007/978-3-540-48085-3_4
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/978-3-662-05138-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023426236
103 https://doi.org/10.1007/978-3-662-05138-2
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bfb0017444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010989701
106 https://doi.org/10.1007/bfb0017444
107 rdf:type schema:CreativeWork
108 https://app.dimensions.ai/details/publication/pub.1023426236 schema:CreativeWork
109 https://doi.org/10.1006/jsco.1995.1036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037014399
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1006/jsco.2002.0541 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051189609
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/0304-3975(96)00042-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028523527
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/s0304-3975(01)00332-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031930886
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/s0743-1066(98)10005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000275719
118 rdf:type schema:CreativeWork
119 https://www.grid.ac/institutes/grid.187323.c schema:alternateName German University in Cairo
120 schema:name Faculty of Information Engineering and Technology, German University Cairo, Egypt
121 rdf:type schema:Organization
122 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
123 schema:name Computer Science Faculty, University of Ulm, Germany
124 rdf:type schema:Organization
 




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


...