Operational Equivalence of CHR Programs and Constraints View Full Text


Ontology type: schema:Chapter     


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

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/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, D-80538, Munich, Germany", 
          "id": "http://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": "Computer Science Department, University of Munich, Oettingenstr. 67, D-80538, Munich, Germany", 
          "id": "http://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"
      }
    ], 
    "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": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66626-4", 
        "978-3-540-48085-3"
      ], 
      "name": "Principles and Practice of Constraint Programming \u2013 CP\u201999", 
      "type": "Book"
    }, 
    "keywords": [
      "user-defined constraints", 
      "Constraint Handling Rules", 
      "CHR programs", 
      "necessary syntactic condition", 
      "high-level language", 
      "programming language semantics", 
      "syntactic conditions", 
      "operational equivalence", 
      "constraint solver", 
      "sufficient syntactic condition", 
      "language semantics", 
      "Handling Rules", 
      "subclass of programs", 
      "constraints", 
      "solver", 
      "semantics", 
      "different programs", 
      "language", 
      "scratch", 
      "rules", 
      "program", 
      "notion", 
      "equivalence", 
      "practical reasons", 
      "fundamental questions", 
      "terminating", 
      "subclasses", 
      "reasons", 
      "questions", 
      "conditions", 
      "paper", 
      "confluent CHR programs"
    ], 
    "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"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "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": "2021-11-01T19:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_71.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-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.

99 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-48085-3_4 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N351c2111e1e94d448a3ddde8eaca532b
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 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.
7 schema:editor N8edefaf5933749598d780bcce4a7d98d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ned684a32ee2f49a583d964cf23cc6cf5
12 schema:keywords CHR programs
13 Constraint Handling Rules
14 Handling Rules
15 conditions
16 confluent CHR programs
17 constraint solver
18 constraints
19 different programs
20 equivalence
21 fundamental questions
22 high-level language
23 language
24 language semantics
25 necessary syntactic condition
26 notion
27 operational equivalence
28 paper
29 practical reasons
30 program
31 programming language semantics
32 questions
33 reasons
34 rules
35 scratch
36 semantics
37 solver
38 subclass of programs
39 subclasses
40 sufficient syntactic condition
41 syntactic conditions
42 terminating
43 user-defined constraints
44 schema:name Operational Equivalence of CHR Programs and Constraints
45 schema:pagination 43-57
46 schema:productId N68b1bf2169ed4505a08956f1efeb7431
47 N701bf0b96d3b47ce82755846699e632a
48 schema:publisher N9727bb1b1a954a9c963125476df41e69
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050960545
50 https://doi.org/10.1007/978-3-540-48085-3_4
51 schema:sdDatePublished 2021-11-01T19:02
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N734c96ae545e4b8d9a8e16b6561adc58
54 schema:url https://doi.org/10.1007/978-3-540-48085-3_4
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N340066609c1c4b669b23e6d0e48b3f2f schema:familyName Jaffar
59 schema:givenName Joxan
60 rdf:type schema:Person
61 N351c2111e1e94d448a3ddde8eaca532b rdf:first sg:person.010445445574.13
62 rdf:rest Nd2a6d473ea664881b5ffc12f32ba1fe6
63 N68b1bf2169ed4505a08956f1efeb7431 schema:name doi
64 schema:value 10.1007/978-3-540-48085-3_4
65 rdf:type schema:PropertyValue
66 N701bf0b96d3b47ce82755846699e632a schema:name dimensions_id
67 schema:value pub.1050960545
68 rdf:type schema:PropertyValue
69 N734c96ae545e4b8d9a8e16b6561adc58 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N8edefaf5933749598d780bcce4a7d98d rdf:first N340066609c1c4b669b23e6d0e48b3f2f
72 rdf:rest rdf:nil
73 N9727bb1b1a954a9c963125476df41e69 schema:name Springer Nature
74 rdf:type schema:Organisation
75 Nd2a6d473ea664881b5ffc12f32ba1fe6 rdf:first sg:person.013750414271.15
76 rdf:rest rdf:nil
77 Ned684a32ee2f49a583d964cf23cc6cf5 schema:isbn 978-3-540-48085-3
78 978-3-540-66626-4
79 schema:name Principles and Practice of Constraint Programming – CP’99
80 rdf:type schema:Book
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
85 schema:name Computer Software
86 rdf:type schema:DefinedTerm
87 sg:person.010445445574.13 schema:affiliation grid-institutes:grid.5252.0
88 schema:familyName Abdennadher
89 schema:givenName Slim
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445445574.13
91 rdf:type schema:Person
92 sg:person.013750414271.15 schema:affiliation grid-institutes:grid.5252.0
93 schema:familyName Frühwirth
94 schema:givenName Thom
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
96 rdf:type schema:Person
97 grid-institutes:grid.5252.0 schema:alternateName Computer Science Department, University of Munich, Oettingenstr. 67, D-80538, Munich, Germany
98 schema:name Computer Science Department, University of Munich, Oettingenstr. 67, D-80538, Munich, Germany
99 rdf:type schema:Organization
 




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


...