Operational Equivalence of CHR Programs and Constraints View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999

AUTHORS

Slim Abdennadher , Thom Frühwirth

ABSTRACT

A fundamental question in programming language semantics is when two programs should be considered equivalent. In this paper we introduce a notion of operational equivalence for CHR programs and user-defined constraints. Constraint Handling Rules (CHR) is a high-level language for writing constraint solvers either from scratch or by modifying existing solvers. We give a decidable, sufficient and necessary syntactic condition for operational equivalence of terminating and confluent CHR programs. For practical reasons, we also investigate a notion of operational equivalence for user-defined constraints that are defined in different programs. We give a sufficient syntactic condition for constraints defined in terminating and confluent CHR programs. For a subclass of programs which have only one user-defined constraint in common, we are able to give a sufficient and necessary syntactic condition. More... »

PAGES

43-57

References to SciGraph publications

  • 1998. Unfold/fold transformations of CCP programs in CONCUR'98 CONCURRENCY THEORY
  • 1986. Equivalences of logic programs in THIRD INTERNATIONAL CONFERENCE ON LOGIC PROGRAMMING
  • 1996. On confluence of Constraint Handling Rules in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP96
  • 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
  • Book

    TITLE

    Principles and Practice of Constraint Programming – CP’99

    ISBN

    978-3-540-66626-4
    978-3-540-48085-3

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-48085-3_4

    DOI

    http://dx.doi.org/10.1007/978-3-540-48085-3_4

    DIMENSIONS

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


    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/2004", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Linguistics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Language, Communication and Culture", 
            "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, D-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": "Ludwig Maximilian University of Munich", 
              "id": "https://www.grid.ac/institutes/grid.5252.0", 
              "name": [
                "Computer Science Department, University of Munich, Oettingenstr. 67, D-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"
          }
        ], 
        "citation": [
          {
            "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-16492-8_91", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011017227", 
              "https://doi.org/10.1007/3-540-16492-8_91"
            ], 
            "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/bfb0055633", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046297034", 
              "https://doi.org/10.1007/bfb0055633"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.1995.1138", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051424940"
            ], 
            "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": "1999", 
        "datePublishedReg": "1999-01-01", 
        "description": "A fundamental question in programming language semantics is when two programs should be considered equivalent. In this paper we introduce a notion of operational equivalence for CHR programs and user-defined constraints. Constraint Handling Rules (CHR) is a high-level language for writing constraint solvers either from scratch or by modifying existing solvers. We give a decidable, sufficient and necessary syntactic condition for operational equivalence of terminating and confluent CHR programs. For practical reasons, we also investigate a notion of operational equivalence for user-defined constraints that are defined in different programs. We give a sufficient syntactic condition for constraints defined in terminating and confluent CHR programs. For a subclass of programs which have only one user-defined constraint in common, we are able to give a sufficient and necessary syntactic condition.", 
        "editor": [
          {
            "familyName": "Jaffar", 
            "givenName": "Joxan", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-48085-3_4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-66626-4", 
            "978-3-540-48085-3"
          ], 
          "name": "Principles and Practice of Constraint Programming \u2013 CP\u201999", 
          "type": "Book"
        }, 
        "name": "Operational Equivalence of CHR Programs and Constraints", 
        "pagination": "43-57", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1050960545"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-48085-3_4"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f2c216f2cb220d64bd90f7e758a767aa5f5953c0926a1984e7e5b133d8b2acf3"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-48085-3_4", 
          "https://app.dimensions.ai/details/publication/pub.1050960545"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:31", 
        "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/0000000364_0000000364/records_72836_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-48085-3_4"
      }
    ]
     

    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-48085-3_4'

    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-48085-3_4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-48085-3_4'

    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-48085-3_4'


     

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

    95 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-48085-3_4 schema:about anzsrc-for:20
    2 anzsrc-for:2004
    3 schema:author N6763cdfc357e45108d407afa81b5c59b
    4 schema:citation sg:pub.10.1007/3-540-16492-8_91
    5 sg:pub.10.1007/3-540-49481-2_4
    6 sg:pub.10.1007/3-540-61551-2_62
    7 sg:pub.10.1007/bfb0017444
    8 sg:pub.10.1007/bfb0055633
    9 https://doi.org/10.1006/inco.1995.1138
    10 schema:datePublished 1999
    11 schema:datePublishedReg 1999-01-01
    12 schema:description A fundamental question in programming language semantics is when two programs should be considered equivalent. In this paper we introduce a notion of operational equivalence for CHR programs and user-defined constraints. Constraint Handling Rules (CHR) is a high-level language for writing constraint solvers either from scratch or by modifying existing solvers. We give a decidable, sufficient and necessary syntactic condition for operational equivalence of terminating and confluent CHR programs. For practical reasons, we also investigate a notion of operational equivalence for user-defined constraints that are defined in different programs. We give a sufficient syntactic condition for constraints defined in terminating and confluent CHR programs. For a subclass of programs which have only one user-defined constraint in common, we are able to give a sufficient and necessary syntactic condition.
    13 schema:editor N010d4e1a8cd24b4bb4778ef7ff37dc2a
    14 schema:genre chapter
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf Nf20e49949693405a86f7079edc897454
    18 schema:name Operational Equivalence of CHR Programs and Constraints
    19 schema:pagination 43-57
    20 schema:productId N0e6ffe1ad64443ed8df5084e587e1cfb
    21 N4e1f112805fd4bf5ad371fed08e754ec
    22 Ne5658c7291a54c388ce240ef96dae3d1
    23 schema:publisher Nb5a8fe05b51b4220a3fb24a5af212318
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050960545
    25 https://doi.org/10.1007/978-3-540-48085-3_4
    26 schema:sdDatePublished 2019-04-16T08:31
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher N56c2f1457e844e8c8eddacbfdc92b4f2
    29 schema:url https://link.springer.com/10.1007%2F978-3-540-48085-3_4
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset chapters
    32 rdf:type schema:Chapter
    33 N010d4e1a8cd24b4bb4778ef7ff37dc2a rdf:first N6bdb56ab4cbd461aab5d14d3833d1443
    34 rdf:rest rdf:nil
    35 N0e6ffe1ad64443ed8df5084e587e1cfb schema:name readcube_id
    36 schema:value f2c216f2cb220d64bd90f7e758a767aa5f5953c0926a1984e7e5b133d8b2acf3
    37 rdf:type schema:PropertyValue
    38 N4e1f112805fd4bf5ad371fed08e754ec schema:name dimensions_id
    39 schema:value pub.1050960545
    40 rdf:type schema:PropertyValue
    41 N56c2f1457e844e8c8eddacbfdc92b4f2 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N6763cdfc357e45108d407afa81b5c59b rdf:first sg:person.010445445574.13
    44 rdf:rest N963cea7cf70f435c8e1e28525071dcd7
    45 N6bdb56ab4cbd461aab5d14d3833d1443 schema:familyName Jaffar
    46 schema:givenName Joxan
    47 rdf:type schema:Person
    48 N963cea7cf70f435c8e1e28525071dcd7 rdf:first sg:person.013750414271.15
    49 rdf:rest rdf:nil
    50 Nb5a8fe05b51b4220a3fb24a5af212318 schema:location Berlin, Heidelberg
    51 schema:name Springer Berlin Heidelberg
    52 rdf:type schema:Organisation
    53 Ne5658c7291a54c388ce240ef96dae3d1 schema:name doi
    54 schema:value 10.1007/978-3-540-48085-3_4
    55 rdf:type schema:PropertyValue
    56 Nf20e49949693405a86f7079edc897454 schema:isbn 978-3-540-48085-3
    57 978-3-540-66626-4
    58 schema:name Principles and Practice of Constraint Programming – CP’99
    59 rdf:type schema:Book
    60 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
    61 schema:name Language, Communication and Culture
    62 rdf:type schema:DefinedTerm
    63 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Linguistics
    65 rdf:type schema:DefinedTerm
    66 sg:person.010445445574.13 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
    67 schema:familyName Abdennadher
    68 schema:givenName Slim
    69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
    70 rdf:type schema:Person
    71 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.5252.0
    72 schema:familyName Frühwirth
    73 schema:givenName Thom
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
    75 rdf:type schema:Person
    76 sg:pub.10.1007/3-540-16492-8_91 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011017227
    77 https://doi.org/10.1007/3-540-16492-8_91
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/3-540-49481-2_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053677545
    80 https://doi.org/10.1007/3-540-49481-2_4
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/3-540-61551-2_62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024772408
    83 https://doi.org/10.1007/3-540-61551-2_62
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/bfb0017444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010989701
    86 https://doi.org/10.1007/bfb0017444
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/bfb0055633 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046297034
    89 https://doi.org/10.1007/bfb0055633
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1006/inco.1995.1138 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051424940
    92 rdf:type schema:CreativeWork
    93 https://www.grid.ac/institutes/grid.5252.0 schema:alternateName Ludwig Maximilian University of Munich
    94 schema:name Computer Science Department, University of Munich, Oettingenstr. 67, D-80538, Munich, Germany
    95 rdf:type schema:Organization
     




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


    ...