Affine Consistency and the Complexity of Semilinear Constraints View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Peter Jonsson , Johan Thapper

ABSTRACT

A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning, just to mention a few examples. We concentrate on relations over the reals and rational numbers. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets Γ of semilinear relations containing the relations R + = {(x,y,z) | x + y = z}, ≤, and {1}. These problems correspond to extensions of LP feasibility. We generalise this result as follows. We introduce an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. This allows us to fully determine the complexity of CSP(Γ) for semilinear Γ containing R + and satisfying two auxiliary conditions. Our result covers all semilinear Γ such that {R + ,{1}} ⊆ Γ. We continue by studying the more general case when Γ contains R + but violates either of the two auxiliary conditions. We show that each such problem is equivalent to a problem in which the relations are finite unions of homogeneous linear sets and we present evidence that determining the complexity of these problems may be highly non-trivial. More... »

PAGES

420-431

References to SciGraph publications

  • 2008. Non-dichotomies in Constraint Satisfaction Complexity in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Book

    TITLE

    Mathematical Foundations of Computer Science 2014

    ISBN

    978-3-662-44464-1
    978-3-662-44465-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-662-44465-8_36

    DOI

    http://dx.doi.org/10.1007/978-3-662-44465-8_36

    DIMENSIONS

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


    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": "Link\u00f6ping University", 
              "id": "https://www.grid.ac/institutes/grid.5640.7", 
              "name": [
                "Department of Computer and Information Science, Link\u00f6ping University, Sweden"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jonsson", 
            "givenName": "Peter", 
            "id": "sg:person.016365414553.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016365414553.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratoire d'Informatique Gaspard-Monge", 
              "id": "https://www.grid.ac/institutes/grid.462940.d", 
              "name": [
                "LIGM, Universit\u00e9 Paris-Est Marne-la-Vall\u00e9e, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Thapper", 
            "givenName": "Johan", 
            "id": "sg:person.011174650517.63", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011174650517.63"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-70583-3_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003879973", 
              "https://doi.org/10.1007/978-3-540-70583-3_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1120582.1120584", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007118300"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.artint.2012.10.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025118537"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cosrev.2008.10.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026304855"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/167088.167245", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035149403"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/logcom/exr011", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059876397"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539700376676", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879250"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2168/lmcs-8(4:5)2012", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069151246"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014", 
        "datePublishedReg": "2014-01-01", 
        "description": "A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning, just to mention a few examples. We concentrate on relations over the reals and rational numbers. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets \u0393 of semilinear relations containing the relations R \u2009+\u2009\u2009=\u2009{(x,y,z) \u00a0 | \u00a0 x\u2009+\u2009y\u2009=\u2009z}, \u2264, and {1}. These problems correspond to extensions of LP feasibility. We generalise this result as follows. We introduce an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. This allows us to fully determine the complexity of CSP(\u0393) for semilinear \u0393 containing R \u2009+\u2009 and satisfying two auxiliary conditions. Our result covers all semilinear \u0393 such that {R \u2009+\u2009,{1}}\u2009\u2286\u2009\u0393. We continue by studying the more general case when \u0393 contains R \u2009+\u2009 but violates either of the two auxiliary conditions. We show that each such problem is equivalent to a problem in which the relations are finite unions of homogeneous linear sets and we present evidence that determining the complexity of these problems may be highly non-trivial.", 
        "editor": [
          {
            "familyName": "Csuhaj-Varj\u00fa", 
            "givenName": "Erzs\u00e9bet", 
            "type": "Person"
          }, 
          {
            "familyName": "Dietzfelbinger", 
            "givenName": "Martin", 
            "type": "Person"
          }, 
          {
            "familyName": "\u00c9sik", 
            "givenName": "Zolt\u00e1n", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-662-44465-8_36", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-662-44464-1", 
            "978-3-662-44465-8"
          ], 
          "name": "Mathematical Foundations of Computer Science 2014", 
          "type": "Book"
        }, 
        "name": "Affine Consistency and the Complexity of Semilinear Constraints", 
        "pagination": "420-431", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-662-44465-8_36"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b3fb6dab1068fc5933f27822a866fcae08e8e5489eea95cbbd382b5a9a6da3a6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1037782018"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-662-44465-8_36", 
          "https://app.dimensions.ai/details/publication/pub.1037782018"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T13:29", 
        "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_8664_00000266.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-662-44465-8_36"
      }
    ]
     

    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-662-44465-8_36'

    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-662-44465-8_36'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-44465-8_36'

    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-662-44465-8_36'


     

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

    110 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-662-44465-8_36 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nc40e99cc4f1d4f53b34d895711001e89
    4 schema:citation sg:pub.10.1007/978-3-540-70583-3_16
    5 https://doi.org/10.1016/j.artint.2012.10.001
    6 https://doi.org/10.1016/j.cosrev.2008.10.003
    7 https://doi.org/10.1093/logcom/exr011
    8 https://doi.org/10.1137/s0097539700376676
    9 https://doi.org/10.1145/1120582.1120584
    10 https://doi.org/10.1145/167088.167245
    11 https://doi.org/10.2168/lmcs-8(4:5)2012
    12 schema:datePublished 2014
    13 schema:datePublishedReg 2014-01-01
    14 schema:description A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning, just to mention a few examples. We concentrate on relations over the reals and rational numbers. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets Γ of semilinear relations containing the relations R  +  = {(x,y,z)   |   x + y = z}, ≤, and {1}. These problems correspond to extensions of LP feasibility. We generalise this result as follows. We introduce an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. This allows us to fully determine the complexity of CSP(Γ) for semilinear Γ containing R  +  and satisfying two auxiliary conditions. Our result covers all semilinear Γ such that {R  + ,{1}} ⊆ Γ. We continue by studying the more general case when Γ contains R  +  but violates either of the two auxiliary conditions. We show that each such problem is equivalent to a problem in which the relations are finite unions of homogeneous linear sets and we present evidence that determining the complexity of these problems may be highly non-trivial.
    15 schema:editor Nab7318c4982a42a0b40e1f665e25ccc4
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf N22ea4f0fab024265ac47cc124173d511
    20 schema:name Affine Consistency and the Complexity of Semilinear Constraints
    21 schema:pagination 420-431
    22 schema:productId N0939b5261d2241d68cb559c2aa7d1b24
    23 N8b92388d10074d389af66b62537f5417
    24 N998879b9e62a43348deb04d7b1dbfb27
    25 schema:publisher N002356e1eb624fc79011b409510df093
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037782018
    27 https://doi.org/10.1007/978-3-662-44465-8_36
    28 schema:sdDatePublished 2019-04-15T13:29
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N8356e8d95ebf4cdf978f907d57ea7995
    31 schema:url http://link.springer.com/10.1007/978-3-662-44465-8_36
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N002356e1eb624fc79011b409510df093 schema:location Berlin, Heidelberg
    36 schema:name Springer Berlin Heidelberg
    37 rdf:type schema:Organisation
    38 N0939b5261d2241d68cb559c2aa7d1b24 schema:name readcube_id
    39 schema:value b3fb6dab1068fc5933f27822a866fcae08e8e5489eea95cbbd382b5a9a6da3a6
    40 rdf:type schema:PropertyValue
    41 N22ea4f0fab024265ac47cc124173d511 schema:isbn 978-3-662-44464-1
    42 978-3-662-44465-8
    43 schema:name Mathematical Foundations of Computer Science 2014
    44 rdf:type schema:Book
    45 N4886911c91e948adab96b56c3cfa910e rdf:first N9d8a6bac445846e898fa07f785149e66
    46 rdf:rest Nc127a8eb09a24a57bc3e722067860fac
    47 N5095760956634c35b90e1f41afcdc4ac schema:familyName Csuhaj-Varjú
    48 schema:givenName Erzsébet
    49 rdf:type schema:Person
    50 N8356e8d95ebf4cdf978f907d57ea7995 schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 N87f6d2c88c6d406f853ad53802a8bf7b schema:familyName Ésik
    53 schema:givenName Zoltán
    54 rdf:type schema:Person
    55 N8b92388d10074d389af66b62537f5417 schema:name dimensions_id
    56 schema:value pub.1037782018
    57 rdf:type schema:PropertyValue
    58 N998879b9e62a43348deb04d7b1dbfb27 schema:name doi
    59 schema:value 10.1007/978-3-662-44465-8_36
    60 rdf:type schema:PropertyValue
    61 N9d8a6bac445846e898fa07f785149e66 schema:familyName Dietzfelbinger
    62 schema:givenName Martin
    63 rdf:type schema:Person
    64 Nab7318c4982a42a0b40e1f665e25ccc4 rdf:first N5095760956634c35b90e1f41afcdc4ac
    65 rdf:rest N4886911c91e948adab96b56c3cfa910e
    66 Nc127a8eb09a24a57bc3e722067860fac rdf:first N87f6d2c88c6d406f853ad53802a8bf7b
    67 rdf:rest rdf:nil
    68 Nc131585328d3452cb747bed142eff951 rdf:first sg:person.011174650517.63
    69 rdf:rest rdf:nil
    70 Nc40e99cc4f1d4f53b34d895711001e89 rdf:first sg:person.016365414553.65
    71 rdf:rest Nc131585328d3452cb747bed142eff951
    72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Information and Computing Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Computation Theory and Mathematics
    77 rdf:type schema:DefinedTerm
    78 sg:person.011174650517.63 schema:affiliation https://www.grid.ac/institutes/grid.462940.d
    79 schema:familyName Thapper
    80 schema:givenName Johan
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011174650517.63
    82 rdf:type schema:Person
    83 sg:person.016365414553.65 schema:affiliation https://www.grid.ac/institutes/grid.5640.7
    84 schema:familyName Jonsson
    85 schema:givenName Peter
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016365414553.65
    87 rdf:type schema:Person
    88 sg:pub.10.1007/978-3-540-70583-3_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003879973
    89 https://doi.org/10.1007/978-3-540-70583-3_16
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1016/j.artint.2012.10.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025118537
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1016/j.cosrev.2008.10.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026304855
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1093/logcom/exr011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059876397
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1137/s0097539700376676 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879250
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1145/1120582.1120584 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007118300
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1145/167088.167245 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035149403
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.2168/lmcs-8(4:5)2012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069151246
    104 rdf:type schema:CreativeWork
    105 https://www.grid.ac/institutes/grid.462940.d schema:alternateName Laboratoire d'Informatique Gaspard-Monge
    106 schema:name LIGM, Université Paris-Est Marne-la-Vallée, France
    107 rdf:type schema:Organization
    108 https://www.grid.ac/institutes/grid.5640.7 schema:alternateName Linköping University
    109 schema:name Department of Computer and Information Science, Linköping University, Sweden
    110 rdf:type schema:Organization
     




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


    ...