Other things besides number: Abstraction, constraint propagation, and string variable types View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-01

AUTHORS

Joseph Scott

ABSTRACT

In constraint programming (CP), a combinatorial problem is modeled declaratively as a conjunction of constraints, each of which captures some of the combinatorial substructure of the problem. Constraints are more than a modeling convenience: every constraint is partially implemented by an inference algorithm, called a propagator, that rules out some but not necessarily all infeasible candidate values of one or more unknowns in the scope of the constraint. Interleaving propagation with systematic search leads to a powerful and complete solution method, combining a high degree of re-usability with natural, high-level modeling. A propagator can be characterized as a sound approximation of a constraint on an abstraction of sets of candidate values; propagators that share an abstraction are similar in the strength of the inference they perform when identifying infeasible candidate values. In this thesis, we consider abstractions of sets of candidate values that may be described by an elegant mathematical formalism, the Galois connection. We develop a theoretical framework from the correspondence between Galois connections and propagators, unifying two disparate views of the abstraction-propagation connection, namely the oft-overlooked distinction between representational and computational over-approximations. Our framework yields compact definitions of propagator strength, even in complicated cases (i.e., involving several types, or unknowns with internal structure); it also yields a method for the principled derivation of propagators from constraint definitions. We apply this framework to the extension of an existing CP solver to constraints over strings, that is, words of finite length. We define, via a Galois connection, an over-approximation for bounded-length strings, and demonstrate two different methods for implementing this over-approximation in a CP solver. First we use the Galois connection to derive a bounded-length string representation as an aggregation of existing scalar types; propagators for this representation are obtained by manual derivation, or automated synthesis, or a combination. Then we implement a string variable type, motivating design choices with knowledge gained from the construction of the over-approximation. The resulting CP solver extension not only substantially eases modeling for combinatorial string problems, but also leads to substantial efficiency improvements over prior CP methods. More... »

PAGES

99-100

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10601-016-9263-9

DOI

http://dx.doi.org/10.1007/s10601-016-9263-9

DIMENSIONS

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


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": "Uppsala University", 
          "id": "https://www.grid.ac/institutes/grid.8993.b", 
          "name": [
            "Department of Information Technology, Division of Computing Science, Uppsala University, Box 337, 75105, Uppsala, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Scott", 
        "givenName": "Joseph", 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-01", 
    "datePublishedReg": "2017-01-01", 
    "description": "In constraint programming (CP), a combinatorial problem is modeled declaratively as a conjunction of constraints, each of which captures some of the combinatorial substructure of the problem. Constraints are more than a modeling convenience: every constraint is partially implemented by an inference algorithm, called a propagator, that rules out some but not necessarily all infeasible candidate values of one or more unknowns in the scope of the constraint. Interleaving propagation with systematic search leads to a powerful and complete solution method, combining a high degree of re-usability with natural, high-level modeling. A propagator can be characterized as a sound approximation of a constraint on an abstraction of sets of candidate values; propagators that share an abstraction are similar in the strength of the inference they perform when identifying infeasible candidate values. In this thesis, we consider abstractions of sets of candidate values that may be described by an elegant mathematical formalism, the Galois connection. We develop a theoretical framework from the correspondence between Galois connections and propagators, unifying two disparate views of the abstraction-propagation connection, namely the oft-overlooked distinction between representational and computational over-approximations. Our framework yields compact definitions of propagator strength, even in complicated cases (i.e., involving several types, or unknowns with internal structure); it also yields a method for the principled derivation of propagators from constraint definitions. We apply this framework to the extension of an existing CP solver to constraints over strings, that is, words of finite length. We define, via a Galois connection, an over-approximation for bounded-length strings, and demonstrate two different methods for implementing this over-approximation in a CP solver. First we use the Galois connection to derive a bounded-length string representation as an aggregation of existing scalar types; propagators for this representation are obtained by manual derivation, or automated synthesis, or a combination. Then we implement a string variable type, motivating design choices with knowledge gained from the construction of the over-approximation. The resulting CP solver extension not only substantially eases modeling for combinatorial string problems, but also leads to substantial efficiency improvements over prior CP methods.", 
    "genre": "non_research_article", 
    "id": "sg:pub.10.1007/s10601-016-9263-9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1043977", 
        "issn": [
          "1383-7133", 
          "1572-9354"
        ], 
        "name": "Constraints", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "22"
      }
    ], 
    "name": "Other things besides number: Abstraction, constraint propagation, and string variable types", 
    "pagination": "99-100", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0425bf6b966c0afa54a7f610fcb6c2b503cbfd1bf8bd29ad11c05daceba2d813"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10601-016-9263-9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000870660"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10601-016-9263-9", 
      "https://app.dimensions.ai/details/publication/pub.1000870660"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:24", 
    "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/0000000362_0000000362/records_87097_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10601-016-9263-9"
  }
]
 

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/s10601-016-9263-9'

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/s10601-016-9263-9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9263-9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9263-9'


 

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

60 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10601-016-9263-9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd552f074e4b14e86bd43303ef908e257
4 schema:datePublished 2017-01
5 schema:datePublishedReg 2017-01-01
6 schema:description In constraint programming (CP), a combinatorial problem is modeled declaratively as a conjunction of constraints, each of which captures some of the combinatorial substructure of the problem. Constraints are more than a modeling convenience: every constraint is partially implemented by an inference algorithm, called a propagator, that rules out some but not necessarily all infeasible candidate values of one or more unknowns in the scope of the constraint. Interleaving propagation with systematic search leads to a powerful and complete solution method, combining a high degree of re-usability with natural, high-level modeling. A propagator can be characterized as a sound approximation of a constraint on an abstraction of sets of candidate values; propagators that share an abstraction are similar in the strength of the inference they perform when identifying infeasible candidate values. In this thesis, we consider abstractions of sets of candidate values that may be described by an elegant mathematical formalism, the Galois connection. We develop a theoretical framework from the correspondence between Galois connections and propagators, unifying two disparate views of the abstraction-propagation connection, namely the oft-overlooked distinction between representational and computational over-approximations. Our framework yields compact definitions of propagator strength, even in complicated cases (i.e., involving several types, or unknowns with internal structure); it also yields a method for the principled derivation of propagators from constraint definitions. We apply this framework to the extension of an existing CP solver to constraints over strings, that is, words of finite length. We define, via a Galois connection, an over-approximation for bounded-length strings, and demonstrate two different methods for implementing this over-approximation in a CP solver. First we use the Galois connection to derive a bounded-length string representation as an aggregation of existing scalar types; propagators for this representation are obtained by manual derivation, or automated synthesis, or a combination. Then we implement a string variable type, motivating design choices with knowledge gained from the construction of the over-approximation. The resulting CP solver extension not only substantially eases modeling for combinatorial string problems, but also leads to substantial efficiency improvements over prior CP methods.
7 schema:genre non_research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N57bfde35bdca4c7d9f949fe9385eceb6
11 Nbaecc9a8c06d44bdba7050aae6357039
12 sg:journal.1043977
13 schema:name Other things besides number: Abstraction, constraint propagation, and string variable types
14 schema:pagination 99-100
15 schema:productId N757b2dae76d64305b261d38aa219b0fe
16 Ne3b9c303dc374921a980593cb827cfa5
17 Ne48b345e57904b8ea8d4fd014726cf03
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000870660
19 https://doi.org/10.1007/s10601-016-9263-9
20 schema:sdDatePublished 2019-04-11T12:24
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N218b670a0112431480058439a3100a26
23 schema:url https://link.springer.com/10.1007%2Fs10601-016-9263-9
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N218b670a0112431480058439a3100a26 schema:name Springer Nature - SN SciGraph project
28 rdf:type schema:Organization
29 N57bfde35bdca4c7d9f949fe9385eceb6 schema:volumeNumber 22
30 rdf:type schema:PublicationVolume
31 N757b2dae76d64305b261d38aa219b0fe schema:name doi
32 schema:value 10.1007/s10601-016-9263-9
33 rdf:type schema:PropertyValue
34 N9ac315e245f24aab9bf81c3f518d1e3e schema:affiliation https://www.grid.ac/institutes/grid.8993.b
35 schema:familyName Scott
36 schema:givenName Joseph
37 rdf:type schema:Person
38 Nbaecc9a8c06d44bdba7050aae6357039 schema:issueNumber 1
39 rdf:type schema:PublicationIssue
40 Nd552f074e4b14e86bd43303ef908e257 rdf:first N9ac315e245f24aab9bf81c3f518d1e3e
41 rdf:rest rdf:nil
42 Ne3b9c303dc374921a980593cb827cfa5 schema:name readcube_id
43 schema:value 0425bf6b966c0afa54a7f610fcb6c2b503cbfd1bf8bd29ad11c05daceba2d813
44 rdf:type schema:PropertyValue
45 Ne48b345e57904b8ea8d4fd014726cf03 schema:name dimensions_id
46 schema:value pub.1000870660
47 rdf:type schema:PropertyValue
48 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
49 schema:name Information and Computing Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
52 schema:name Computation Theory and Mathematics
53 rdf:type schema:DefinedTerm
54 sg:journal.1043977 schema:issn 1383-7133
55 1572-9354
56 schema:name Constraints
57 rdf:type schema:Periodical
58 https://www.grid.ac/institutes/grid.8993.b schema:alternateName Uppsala University
59 schema:name Department of Information Technology, Division of Computing Science, Uppsala University, Box 337, 75105, Uppsala, Sweden
60 rdf:type schema:Organization
 




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


...