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

References to SciGraph publications

  • 2001. Combining Constraint Solving in CONSTRAINTS IN COMPUTATIONAL LOGICS
  • 2000. Better Communication for Tighter Cooperation in COMPUTATIONAL LOGIC — CL 2000
  • 2005-06-10. Operational semantics and confluence of constraint propagation rules in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING-CP97
  • 1999-06-11. On Completion of Constraint Handling Rules in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP98
  • 2000. Proving Termination of Constraint Solver Programs in NEW TRENDS IN CONSTRAINTS
  • 2001. Basic Operators for Solving Constraints via Collaboration of Solvers in ARTIFICIAL INTELLIGENCE AND SYMBOLIC COMPUTATION
  • 1999. Operational Equivalence of CHR Programs and Constraints in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP’99
  • 2003. Essentials of Constraint Programming in NONE
  • 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 N926cd26af96a4d9592c159be74f799f5
    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 Ne185c8dd4b0244dd803d73f408b8de91
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree true
    25 schema:isPartOf Nbd378218a67f46e4869a91b9baeb8262
    26 schema:name Integration and Optimization of Rule-Based Constraint Solvers
    27 schema:pagination 198-213
    28 schema:productId N08a8589396684baab2ab034acc93794c
    29 N5fe5d23f75c942729b44b74a001b873b
    30 N8bfd6b7b9e5f417c99668c7bf1ef4065
    31 schema:publisher N6ca85add92474a53b9cf84bc57c7ec61
    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 N61b8f71fc282465ab25dea9f2439703e
    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 N08a8589396684baab2ab034acc93794c schema:name readcube_id
    42 schema:value 8f5131af1fd2dce4248d6ad2a7abee9a0374aa5517e596d6ec7cbc8277c39d24
    43 rdf:type schema:PropertyValue
    44 N5fe5d23f75c942729b44b74a001b873b schema:name dimensions_id
    45 schema:value pub.1030083923
    46 rdf:type schema:PropertyValue
    47 N61b8f71fc282465ab25dea9f2439703e schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N6ca85add92474a53b9cf84bc57c7ec61 schema:location Berlin, Heidelberg
    50 schema:name Springer Berlin Heidelberg
    51 rdf:type schema:Organisation
    52 N8bfd6b7b9e5f417c99668c7bf1ef4065 schema:name doi
    53 schema:value 10.1007/978-3-540-25938-1_17
    54 rdf:type schema:PropertyValue
    55 N926cd26af96a4d9592c159be74f799f5 rdf:first sg:person.010445445574.13
    56 rdf:rest Ne7fba5825b754b9f92a874300b72eaea
    57 Nbd378218a67f46e4869a91b9baeb8262 schema:isbn 978-3-540-22174-6
    58 978-3-540-25938-1
    59 schema:name Logic Based Program Synthesis and Transformation
    60 rdf:type schema:Book
    61 Ne185c8dd4b0244dd803d73f408b8de91 rdf:first Nf00ab1947d5f4007bc04a61d07ec23cb
    62 rdf:rest rdf:nil
    63 Ne7fba5825b754b9f92a874300b72eaea rdf:first sg:person.013750414271.15
    64 rdf:rest rdf:nil
    65 Nf00ab1947d5f4007bc04a61d07ec23cb schema:familyName Bruynooghe
    66 schema:givenName Maurice
    67 rdf:type schema:Person
    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)


    ...