Complexity of a CHR Solver for Existentially Quantified Conjunctions of Equations over Trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007

AUTHORS

Marc Meister , Khalil Djelloul , Thom Frühwirth

ABSTRACT

Constraint Handling Rules (CHR) is a concurrent, committed-choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. We first prove its exponential complexity in time and space for non-flat equations and deduce from this proof a quadratic complexity for flat equations. We then present an extended CHR solver for solving existentially quantified conjunctions of non-flat equations in the theory of finite or infinite trees. We reach a quadratic complexity by first flattening the equations and introducing new existentially quantified variables, then using the classic solver, and finally eliminating particular equations and quantified variables. More... »

PAGES

139-153

References to SciGraph publications

Book

TITLE

Recent Advances in Constraints

ISBN

978-3-540-73816-9

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-73817-6_9

DOI

http://dx.doi.org/10.1007/978-3-540-73817-6_9

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Ulm", 
          "id": "https://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Fakult\u00e4t f\u00fcr Ingenieurwissenschaften und Informatik, Universit\u00e4t Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Meister", 
        "givenName": "Marc", 
        "id": "sg:person.014561740275.66", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014561740275.66"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Ulm", 
          "id": "https://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Fakult\u00e4t f\u00fcr Ingenieurwissenschaften und Informatik, Universit\u00e4t Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Djelloul", 
        "givenName": "Khalil", 
        "id": "sg:person.013371444706.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013371444706.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Ulm", 
          "id": "https://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Fakult\u00e4t f\u00fcr Ingenieurwissenschaften und Informatik, Universit\u00e4t 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": "https://doi.org/10.1145/62.2160", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006789528"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321250.321253", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009195371"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322217.322230", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010875099"
        ], 
        "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": "https://doi.org/10.1016/0022-0000(78)90043-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026664508"
        ], 
        "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.1145/357162.357169", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048463763"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s1471068406002997", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053798040"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s1471068406002997", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053798040"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s1471068405002541", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053824991"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s1471068405002541", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053824991"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/lics.1988.5132", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086223791"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2007", 
    "datePublishedReg": "2007-01-01", 
    "description": "Constraint Handling Rules (CHR) is a concurrent, committed-choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. We first prove its exponential complexity in time and space for non-flat equations and deduce from this proof a quadratic complexity for flat equations. We then present an extended CHR solver for solving existentially quantified conjunctions of non-flat equations in the theory of finite or infinite trees. We reach a quadratic complexity by first flattening the equations and introducing new existentially quantified variables, then using the classic solver, and finally eliminating particular equations and quantified variables.", 
    "editor": [
      {
        "familyName": "Azevedo", 
        "givenName": "Francisco", 
        "type": "Person"
      }, 
      {
        "familyName": "Barahona", 
        "givenName": "Pedro", 
        "type": "Person"
      }, 
      {
        "familyName": "Fages", 
        "givenName": "Fran\u00e7ois", 
        "type": "Person"
      }, 
      {
        "familyName": "Rossi", 
        "givenName": "Francesca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-73817-6_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-73816-9"
      ], 
      "name": "Recent Advances in Constraints", 
      "type": "Book"
    }, 
    "name": "Complexity of a CHR Solver for Existentially Quantified Conjunctions of Equations over Trees", 
    "pagination": "139-153", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-73817-6_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "8a9c4baa071e236f4bf932d4b14209d5869dfe4bb99ae9428f5bd446d5d985b7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029096534"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-73817-6_9", 
      "https://app.dimensions.ai/details/publication/pub.1029096534"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:26", 
    "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/0000000345_0000000345/records_64106_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-73817-6_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/978-3-540-73817-6_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/978-3-540-73817-6_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73817-6_9'

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-73817-6_9'


 

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

130 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-73817-6_9 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nddc19d5490eb44948be14487e9ca9862
4 schema:citation sg:pub.10.1007/11562931_11
5 sg:pub.10.1007/978-3-662-05138-2
6 https://app.dimensions.ai/details/publication/pub.1023426236
7 https://doi.org/10.1016/0022-0000(78)90043-0
8 https://doi.org/10.1016/s0743-1066(98)10005-5
9 https://doi.org/10.1017/s1471068405002541
10 https://doi.org/10.1017/s1471068406002997
11 https://doi.org/10.1109/lics.1988.5132
12 https://doi.org/10.1145/321250.321253
13 https://doi.org/10.1145/322217.322230
14 https://doi.org/10.1145/357162.357169
15 https://doi.org/10.1145/62.2160
16 schema:datePublished 2007
17 schema:datePublishedReg 2007-01-01
18 schema:description Constraint Handling Rules (CHR) is a concurrent, committed-choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. We first prove its exponential complexity in time and space for non-flat equations and deduce from this proof a quadratic complexity for flat equations. We then present an extended CHR solver for solving existentially quantified conjunctions of non-flat equations in the theory of finite or infinite trees. We reach a quadratic complexity by first flattening the equations and introducing new existentially quantified variables, then using the classic solver, and finally eliminating particular equations and quantified variables.
19 schema:editor N4f4ff3e711c04e1bb9ee0a01e70c3186
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf Ne09f86b90d364de0a7035b3f04396645
24 schema:name Complexity of a CHR Solver for Existentially Quantified Conjunctions of Equations over Trees
25 schema:pagination 139-153
26 schema:productId N4235303d0f424f8a9a521fdb97d3aae1
27 N822b3a9997694e2daab5b77895ca906f
28 Nf46624e5d42846a185293c1d9fecdf68
29 schema:publisher Nf2dad676bc214d97b566aa738e94d439
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029096534
31 https://doi.org/10.1007/978-3-540-73817-6_9
32 schema:sdDatePublished 2019-04-16T05:26
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N0cc8d72913c8439fb0d90fae5327ccf7
35 schema:url https://link.springer.com/10.1007%2F978-3-540-73817-6_9
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N00a37c10a2244f36b550d6d154268b86 schema:familyName Fages
40 schema:givenName François
41 rdf:type schema:Person
42 N0cc8d72913c8439fb0d90fae5327ccf7 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N11b9f863b727416d9ebd125868e97519 schema:familyName Barahona
45 schema:givenName Pedro
46 rdf:type schema:Person
47 N4235303d0f424f8a9a521fdb97d3aae1 schema:name doi
48 schema:value 10.1007/978-3-540-73817-6_9
49 rdf:type schema:PropertyValue
50 N4f4ff3e711c04e1bb9ee0a01e70c3186 rdf:first N72af3c37dc824234bdcc3fb236949687
51 rdf:rest N931f88954c5d4136919f8b6fe470db0e
52 N5365c79f8feb4ef0be82b6278fb0769f rdf:first N00a37c10a2244f36b550d6d154268b86
53 rdf:rest Nc36475751a8346b0b81723097d1aac4b
54 N72af3c37dc824234bdcc3fb236949687 schema:familyName Azevedo
55 schema:givenName Francisco
56 rdf:type schema:Person
57 N822b3a9997694e2daab5b77895ca906f schema:name dimensions_id
58 schema:value pub.1029096534
59 rdf:type schema:PropertyValue
60 N931f88954c5d4136919f8b6fe470db0e rdf:first N11b9f863b727416d9ebd125868e97519
61 rdf:rest N5365c79f8feb4ef0be82b6278fb0769f
62 N9acdccfa5f0f4c8cb640ea0a347d72a3 rdf:first sg:person.013371444706.47
63 rdf:rest Nd8674718dc614334bf22d9e2ed13e4c1
64 Nb84ebe8ae2e848b280f9f9f04979ed03 schema:familyName Rossi
65 schema:givenName Francesca
66 rdf:type schema:Person
67 Nc36475751a8346b0b81723097d1aac4b rdf:first Nb84ebe8ae2e848b280f9f9f04979ed03
68 rdf:rest rdf:nil
69 Nd8674718dc614334bf22d9e2ed13e4c1 rdf:first sg:person.013750414271.15
70 rdf:rest rdf:nil
71 Nddc19d5490eb44948be14487e9ca9862 rdf:first sg:person.014561740275.66
72 rdf:rest N9acdccfa5f0f4c8cb640ea0a347d72a3
73 Ne09f86b90d364de0a7035b3f04396645 schema:isbn 978-3-540-73816-9
74 schema:name Recent Advances in Constraints
75 rdf:type schema:Book
76 Nf2dad676bc214d97b566aa738e94d439 schema:location Berlin, Heidelberg
77 schema:name Springer Berlin Heidelberg
78 rdf:type schema:Organisation
79 Nf46624e5d42846a185293c1d9fecdf68 schema:name readcube_id
80 schema:value 8a9c4baa071e236f4bf932d4b14209d5869dfe4bb99ae9428f5bd446d5d985b7
81 rdf:type schema:PropertyValue
82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
83 schema:name Mathematical Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
86 schema:name Pure Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.013371444706.47 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
89 schema:familyName Djelloul
90 schema:givenName Khalil
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013371444706.47
92 rdf:type schema:Person
93 sg:person.013750414271.15 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
94 schema:familyName Frühwirth
95 schema:givenName Thom
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
97 rdf:type schema:Person
98 sg:person.014561740275.66 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
99 schema:familyName Meister
100 schema:givenName Marc
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014561740275.66
102 rdf:type schema:Person
103 sg:pub.10.1007/11562931_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030053121
104 https://doi.org/10.1007/11562931_11
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/978-3-662-05138-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023426236
107 https://doi.org/10.1007/978-3-662-05138-2
108 rdf:type schema:CreativeWork
109 https://app.dimensions.ai/details/publication/pub.1023426236 schema:CreativeWork
110 https://doi.org/10.1016/0022-0000(78)90043-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026664508
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/s0743-1066(98)10005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000275719
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1017/s1471068405002541 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053824991
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1017/s1471068406002997 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053798040
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/lics.1988.5132 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086223791
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/321250.321253 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009195371
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/322217.322230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010875099
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/357162.357169 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048463763
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/62.2160 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006789528
127 rdf:type schema:CreativeWork
128 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
129 schema:name Fakultät für Ingenieurwissenschaften und Informatik, Universität Ulm, Germany
130 rdf:type schema:Organization
 




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


...