Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Thom Frühwirth

ABSTRACT

We give an efficiently executable specification of the global constraint of lexicographic order in the Constraint Handling Rules (CHR) language. In contrast to previous approaches, the implementation is short and concise without giving up on the best known worst case time complexity. It is incremental and concurrent by nature of CHR. It is provably correct and confluent. It is independent of the underlying constraint system, and therefore not restricted to finite domains. We have found a direct recursive decomposition of the problem. We also show completeness of constraint propagation, i.e. that all possible logical consequences of the constraint are generated by the implementation. Finally, we report about some practical implementation experiments. More... »

PAGES

14-28

Book

TITLE

Recent Advances in Constraints

ISBN

978-3-540-34215-1
978-3-540-34216-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11754602_2

DOI

http://dx.doi.org/10.1007/11754602_2

DIMENSIONS

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


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": "Faculty of Computer Science, University of Ulm, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Faculty of Computer Science, 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"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "We give an efficiently executable specification of the global constraint of lexicographic order in the Constraint Handling Rules (CHR) language. In contrast to previous approaches, the implementation is short and concise without giving up on the best known worst case time complexity. It is incremental and concurrent by nature of CHR. It is provably correct and confluent. It is independent of the underlying constraint system, and therefore not restricted to finite domains. We have found a direct recursive decomposition of the problem. We also show completeness of constraint propagation, i.e. that all possible logical consequences of the constraint are generated by the implementation. Finally, we report about some practical implementation experiments.", 
    "editor": [
      {
        "familyName": "Hnich", 
        "givenName": "Brahim", 
        "type": "Person"
      }, 
      {
        "familyName": "Carlsson", 
        "givenName": "Mats", 
        "type": "Person"
      }, 
      {
        "familyName": "Fages", 
        "givenName": "Fran\u00e7ois", 
        "type": "Person"
      }, 
      {
        "familyName": "Rossi", 
        "givenName": "Francesca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11754602_2", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-34215-1", 
        "978-3-540-34216-8"
      ], 
      "name": "Recent Advances in Constraints", 
      "type": "Book"
    }, 
    "keywords": [
      "Constraint Handling Rules (CHR) language", 
      "worst case time complexity", 
      "rule language", 
      "executable specification", 
      "time complexity", 
      "implementation experiments", 
      "constraint propagation", 
      "recursive decomposition", 
      "constraint system", 
      "global constraints", 
      "previous approaches", 
      "propagation rules", 
      "order constraints", 
      "lexicographic order", 
      "finite domain", 
      "arbitrary domains", 
      "constraints", 
      "implementation", 
      "logical consequence", 
      "specification", 
      "complexity", 
      "language", 
      "domain", 
      "rules", 
      "completeness", 
      "system", 
      "decomposition", 
      "order", 
      "experiments", 
      "propagation", 
      "nature", 
      "CHR", 
      "consequences", 
      "contrast", 
      "problem", 
      "approach", 
      "Handling Rules (CHR) language", 
      "case time complexity", 
      "nature of CHR", 
      "direct recursive decomposition", 
      "possible logical consequences", 
      "practical implementation experiments", 
      "Complete Propagation Rules", 
      "Lexicographic Order Constraints"
    ], 
    "name": "Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains", 
    "pagination": "14-28", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023300203"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11754602_2"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11754602_2", 
      "https://app.dimensions.ai/details/publication/pub.1023300203"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:04", 
    "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_84.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11754602_2"
  }
]
 

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/11754602_2'

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/11754602_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11754602_2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11754602_2'


 

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

119 TRIPLES      23 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11754602_2 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author Nb222bcbbe250433c92d6b3c61a5dcfdf
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description We give an efficiently executable specification of the global constraint of lexicographic order in the Constraint Handling Rules (CHR) language. In contrast to previous approaches, the implementation is short and concise without giving up on the best known worst case time complexity. It is incremental and concurrent by nature of CHR. It is provably correct and confluent. It is independent of the underlying constraint system, and therefore not restricted to finite domains. We have found a direct recursive decomposition of the problem. We also show completeness of constraint propagation, i.e. that all possible logical consequences of the constraint are generated by the implementation. Finally, we report about some practical implementation experiments.
7 schema:editor N64628afff1f54196bdbc76f8b2c7600d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7f5518b8434e49e2a4510fda80f14928
12 schema:keywords CHR
13 Complete Propagation Rules
14 Constraint Handling Rules (CHR) language
15 Handling Rules (CHR) language
16 Lexicographic Order Constraints
17 approach
18 arbitrary domains
19 case time complexity
20 completeness
21 complexity
22 consequences
23 constraint propagation
24 constraint system
25 constraints
26 contrast
27 decomposition
28 direct recursive decomposition
29 domain
30 executable specification
31 experiments
32 finite domain
33 global constraints
34 implementation
35 implementation experiments
36 language
37 lexicographic order
38 logical consequence
39 nature
40 nature of CHR
41 order
42 order constraints
43 possible logical consequences
44 practical implementation experiments
45 previous approaches
46 problem
47 propagation
48 propagation rules
49 recursive decomposition
50 rule language
51 rules
52 specification
53 system
54 time complexity
55 worst case time complexity
56 schema:name Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains
57 schema:pagination 14-28
58 schema:productId N4ed01d61359b4f03a72772f7db945027
59 Nd35ae9ca2f1e4cff82c003177d434f02
60 schema:publisher Nfb2f812b0b0b4b568093d1acf7bce594
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023300203
62 https://doi.org/10.1007/11754602_2
63 schema:sdDatePublished 2021-11-01T19:04
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Nf79b8d14e24744f08b4561e9ace94206
66 schema:url https://doi.org/10.1007/11754602_2
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N2a1244347bfe414c922d53e3d81dad72 schema:familyName Rossi
71 schema:givenName Francesca
72 rdf:type schema:Person
73 N4ed01d61359b4f03a72772f7db945027 schema:name doi
74 schema:value 10.1007/11754602_2
75 rdf:type schema:PropertyValue
76 N64628afff1f54196bdbc76f8b2c7600d rdf:first Nb8a9c16b187d413296fc1b34b8961914
77 rdf:rest N8ba209b89b29473ab8898e800186c6fd
78 N6adbad80d8d540e5b41960bf23c5c89e schema:familyName Carlsson
79 schema:givenName Mats
80 rdf:type schema:Person
81 N6e8316f850694620805dc11cc243689b schema:familyName Fages
82 schema:givenName François
83 rdf:type schema:Person
84 N7f5518b8434e49e2a4510fda80f14928 schema:isbn 978-3-540-34215-1
85 978-3-540-34216-8
86 schema:name Recent Advances in Constraints
87 rdf:type schema:Book
88 N85caceb727424784abc012e9f2bb9ef8 rdf:first N6e8316f850694620805dc11cc243689b
89 rdf:rest Naafea807c01b48819ddf96c92b6d0084
90 N8ba209b89b29473ab8898e800186c6fd rdf:first N6adbad80d8d540e5b41960bf23c5c89e
91 rdf:rest N85caceb727424784abc012e9f2bb9ef8
92 Naafea807c01b48819ddf96c92b6d0084 rdf:first N2a1244347bfe414c922d53e3d81dad72
93 rdf:rest rdf:nil
94 Nb222bcbbe250433c92d6b3c61a5dcfdf rdf:first sg:person.013750414271.15
95 rdf:rest rdf:nil
96 Nb8a9c16b187d413296fc1b34b8961914 schema:familyName Hnich
97 schema:givenName Brahim
98 rdf:type schema:Person
99 Nd35ae9ca2f1e4cff82c003177d434f02 schema:name dimensions_id
100 schema:value pub.1023300203
101 rdf:type schema:PropertyValue
102 Nf79b8d14e24744f08b4561e9ace94206 schema:name Springer Nature - SN SciGraph project
103 rdf:type schema:Organization
104 Nfb2f812b0b0b4b568093d1acf7bce594 schema:name Springer Nature
105 rdf:type schema:Organisation
106 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
107 schema:name Information and Computing Sciences
108 rdf:type schema:DefinedTerm
109 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
110 schema:name Computer Software
111 rdf:type schema:DefinedTerm
112 sg:person.013750414271.15 schema:affiliation grid-institutes:grid.6582.9
113 schema:familyName Frühwirth
114 schema:givenName Thom
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
116 rdf:type schema:Person
117 grid-institutes:grid.6582.9 schema:alternateName Faculty of Computer Science, University of Ulm, Germany
118 schema:name Faculty of Computer Science, University of Ulm, Germany
119 rdf:type schema:Organization
 




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


...