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

References to SciGraph publications

  • 2005-06-10. Operational semantics and confluence of constraint propagation rules in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING-CP97
  • 1999-05. Confluence and Semantics of Constraint Simplification Rules in CONSTRAINTS
  • 2005. Parallelizing Union-Find in Constraint Handling Rules Using Confluence Analysis in LOGIC PROGRAMMING
  • 2004. Deriving Filtering Algorithms from Constraint Checkers in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2004
  • 2004. From Constraints to Finite Automata to Filtering Algorithms in PROGRAMMING LANGUAGES AND SYSTEMS
  • 2002. Global Constraints for Lexicographic Orderings in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2002
  • 2003. Essentials of Constraint Programming in NONE
  • Book

    TITLE

    Recent Advances in Constraints

    ISBN

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

    Author Affiliations

    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": "University of Ulm", 
              "id": "https://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"
          }
        ], 
        "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/3-540-46135-3_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000564948", 
              "https://doi.org/10.1007/3-540-46135-3_7"
            ], 
            "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.1023/a:1009842826135", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017229802", 
              "https://doi.org/10.1023/a:1009842826135"
            ], 
            "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": "sg:pub.10.1007/978-3-540-30201-8_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026106998", 
              "https://doi.org/10.1007/978-3-540-30201-8_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30201-8_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026106998", 
              "https://doi.org/10.1007/978-3-540-30201-8_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11562931_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030053121", 
              "https://doi.org/10.1007/11562931_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.entcs.2005.06.039", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038357289"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24725-8_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041095466", 
              "https://doi.org/10.1007/978-3-540-24725-8_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24725-8_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041095466", 
              "https://doi.org/10.1007/978-3-540-24725-8_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781139172752", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098713477"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "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"
        }, 
        "name": "Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains", 
        "pagination": "14-28", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11754602_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6f020d91807eeb5b1fb018b0a5c0bca2066a5ca64fb24a4dadbcc02583f09d43"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1023300203"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11754602_2", 
          "https://app.dimensions.ai/details/publication/pub.1023300203"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T14:58", 
        "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/0000000001_0000000264/records_8669_00000558.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/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      38 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11754602_2 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nf37d7fc65b534861aee2b5461c9bee06
    4 schema:citation sg:pub.10.1007/11562931_11
    5 sg:pub.10.1007/3-540-46135-3_7
    6 sg:pub.10.1007/978-3-540-24725-8_8
    7 sg:pub.10.1007/978-3-540-30201-8_11
    8 sg:pub.10.1007/978-3-662-05138-2
    9 sg:pub.10.1007/bfb0017444
    10 sg:pub.10.1023/a:1009842826135
    11 https://app.dimensions.ai/details/publication/pub.1023426236
    12 https://doi.org/10.1016/j.entcs.2005.06.039
    13 https://doi.org/10.1016/s0743-1066(98)10005-5
    14 https://doi.org/10.1017/cbo9781139172752
    15 schema:datePublished 2006
    16 schema:datePublishedReg 2006-01-01
    17 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.
    18 schema:editor N9e2ee279254e4a8199bf9c932ae37295
    19 schema:genre chapter
    20 schema:inLanguage en
    21 schema:isAccessibleForFree true
    22 schema:isPartOf N62763e641ade446f9b12f8040865acb8
    23 schema:name Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains
    24 schema:pagination 14-28
    25 schema:productId N1a6f73cbc467477ca057a5b827404c3a
    26 Ndfb6c157f3e146fbb823122f4d9296f4
    27 Nf0ee9c8d6160434984baceef158d8226
    28 schema:publisher N317ddaf877044b1596f224873c2165d7
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023300203
    30 https://doi.org/10.1007/11754602_2
    31 schema:sdDatePublished 2019-04-15T14:58
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher Na3d3a16c381f49218dba93bfff3c00e3
    34 schema:url http://link.springer.com/10.1007/11754602_2
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset chapters
    37 rdf:type schema:Chapter
    38 N1690848051e9447a99199a924698d064 schema:familyName Fages
    39 schema:givenName François
    40 rdf:type schema:Person
    41 N1a6f73cbc467477ca057a5b827404c3a schema:name readcube_id
    42 schema:value 6f020d91807eeb5b1fb018b0a5c0bca2066a5ca64fb24a4dadbcc02583f09d43
    43 rdf:type schema:PropertyValue
    44 N317ddaf877044b1596f224873c2165d7 schema:location Berlin, Heidelberg
    45 schema:name Springer Berlin Heidelberg
    46 rdf:type schema:Organisation
    47 N623e672486ef42f88991d44189536601 schema:familyName Rossi
    48 schema:givenName Francesca
    49 rdf:type schema:Person
    50 N62763e641ade446f9b12f8040865acb8 schema:isbn 978-3-540-34215-1
    51 978-3-540-34216-8
    52 schema:name Recent Advances in Constraints
    53 rdf:type schema:Book
    54 N66eb633ec1b84229ae2abdc8284d062a rdf:first N1690848051e9447a99199a924698d064
    55 rdf:rest Nc0ea6102a2474e93a54241a15f0219c7
    56 N9e2ee279254e4a8199bf9c932ae37295 rdf:first Nfdceb28b17794063a558719177a95f54
    57 rdf:rest Nc04683d1ea33418bb19c3603ca2b789a
    58 Na3d3a16c381f49218dba93bfff3c00e3 schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 Nb6f81904284f4b07aa8af363f8f27a82 schema:familyName Carlsson
    61 schema:givenName Mats
    62 rdf:type schema:Person
    63 Nc04683d1ea33418bb19c3603ca2b789a rdf:first Nb6f81904284f4b07aa8af363f8f27a82
    64 rdf:rest N66eb633ec1b84229ae2abdc8284d062a
    65 Nc0ea6102a2474e93a54241a15f0219c7 rdf:first N623e672486ef42f88991d44189536601
    66 rdf:rest rdf:nil
    67 Ndfb6c157f3e146fbb823122f4d9296f4 schema:name dimensions_id
    68 schema:value pub.1023300203
    69 rdf:type schema:PropertyValue
    70 Nf0ee9c8d6160434984baceef158d8226 schema:name doi
    71 schema:value 10.1007/11754602_2
    72 rdf:type schema:PropertyValue
    73 Nf37d7fc65b534861aee2b5461c9bee06 rdf:first sg:person.013750414271.15
    74 rdf:rest rdf:nil
    75 Nfdceb28b17794063a558719177a95f54 schema:familyName Hnich
    76 schema:givenName Brahim
    77 rdf:type schema:Person
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Computation Theory and Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
    85 schema:familyName Frühwirth
    86 schema:givenName Thom
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
    88 rdf:type schema:Person
    89 sg:pub.10.1007/11562931_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030053121
    90 https://doi.org/10.1007/11562931_11
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/3-540-46135-3_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000564948
    93 https://doi.org/10.1007/3-540-46135-3_7
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-3-540-24725-8_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041095466
    96 https://doi.org/10.1007/978-3-540-24725-8_8
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/978-3-540-30201-8_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026106998
    99 https://doi.org/10.1007/978-3-540-30201-8_11
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/978-3-662-05138-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023426236
    102 https://doi.org/10.1007/978-3-662-05138-2
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/bfb0017444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010989701
    105 https://doi.org/10.1007/bfb0017444
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1023/a:1009842826135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017229802
    108 https://doi.org/10.1023/a:1009842826135
    109 rdf:type schema:CreativeWork
    110 https://app.dimensions.ai/details/publication/pub.1023426236 schema:CreativeWork
    111 https://doi.org/10.1016/j.entcs.2005.06.039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038357289
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/s0743-1066(98)10005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000275719
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1017/cbo9781139172752 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098713477
    116 rdf:type schema:CreativeWork
    117 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
    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)


    ...