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-01-01

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

Book

TITLE

Recent Advances in Constraints

ISBN

978-3-540-73816-9
978-3-540-73817-6

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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Fakult\u00e4t f\u00fcr Ingenieurwissenschaften und Informatik, Universit\u00e4t Ulm, Germany", 
          "id": "http://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": "Fakult\u00e4t f\u00fcr Ingenieurwissenschaften und Informatik, Universit\u00e4t Ulm, Germany", 
          "id": "http://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": "Fakult\u00e4t f\u00fcr Ingenieurwissenschaften und Informatik, Universit\u00e4t Ulm, Germany", 
          "id": "http://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"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "Constraint Handling Rules (CHR) is a concurrent, committed-choice, rule-based language. One of the first CHR\u00a0programs 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", 
        "978-3-540-73817-6"
      ], 
      "name": "Recent Advances in Constraints", 
      "type": "Book"
    }, 
    "keywords": [
      "quantified conjunctions", 
      "quadratic complexity", 
      "CHR solvers", 
      "classic solvers", 
      "particular equation", 
      "rational trees", 
      "equations", 
      "solver", 
      "exponential complexity", 
      "syntactic equality", 
      "quantified variables", 
      "infinite trees", 
      "complexity", 
      "variables", 
      "constraint solver", 
      "deduce", 
      "space", 
      "theory", 
      "Constraint Handling Rules", 
      "proof", 
      "equality", 
      "unification", 
      "rules", 
      "rule-based language", 
      "trees", 
      "conjunction", 
      "Handling Rules", 
      "time", 
      "program", 
      "language", 
      "first CHR", 
      "classic constraint solver", 
      "non-flat equations", 
      "flat equations", 
      "extended CHR solver"
    ], 
    "name": "Complexity of a CHR Solver for Existentially Quantified Conjunctions of Equations over Trees", 
    "pagination": "139-153", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029096534"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-73817-6_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "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": "2021-12-01T20:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_412.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-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.

124 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 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 N75769a83afbc487394a20cbee03827bd
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 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.
7 schema:editor N62c2d3edc0e14f32a5fd23cbbfcce8de
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N64900b35db964a719496e745e4a482ab
12 schema:keywords CHR solvers
13 Constraint Handling Rules
14 Handling Rules
15 classic constraint solver
16 classic solvers
17 complexity
18 conjunction
19 constraint solver
20 deduce
21 equality
22 equations
23 exponential complexity
24 extended CHR solver
25 first CHR
26 flat equations
27 infinite trees
28 language
29 non-flat equations
30 particular equation
31 program
32 proof
33 quadratic complexity
34 quantified conjunctions
35 quantified variables
36 rational trees
37 rule-based language
38 rules
39 solver
40 space
41 syntactic equality
42 theory
43 time
44 trees
45 unification
46 variables
47 schema:name Complexity of a CHR Solver for Existentially Quantified Conjunctions of Equations over Trees
48 schema:pagination 139-153
49 schema:productId N5d48b7cf4cc14d50be62ce3171421bb3
50 Nd88299bbf8aa459b85a36356e3816d64
51 schema:publisher Nc444b5592c814ed8a559ba6f156b3318
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029096534
53 https://doi.org/10.1007/978-3-540-73817-6_9
54 schema:sdDatePublished 2021-12-01T20:09
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N0178bca1401e43caac29769e1f8d1f08
57 schema:url https://doi.org/10.1007/978-3-540-73817-6_9
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N0178bca1401e43caac29769e1f8d1f08 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N09bbc607ac14466aa88525b42fbb1d83 schema:familyName Azevedo
64 schema:givenName Francisco
65 rdf:type schema:Person
66 N1ab8fb622c824da5bb541f930d27ba85 rdf:first sg:person.013371444706.47
67 rdf:rest Ne92a5c3d83184ce8b6fcb260c1e74590
68 N23dcb4ff475e404aaadefc21035325ea schema:familyName Barahona
69 schema:givenName Pedro
70 rdf:type schema:Person
71 N4febb7cb93c24ef1817c643f2c2b814f rdf:first Nb4337801dbe0459f8b6e611c9be3f63c
72 rdf:rest rdf:nil
73 N5d48b7cf4cc14d50be62ce3171421bb3 schema:name doi
74 schema:value 10.1007/978-3-540-73817-6_9
75 rdf:type schema:PropertyValue
76 N62c2d3edc0e14f32a5fd23cbbfcce8de rdf:first N09bbc607ac14466aa88525b42fbb1d83
77 rdf:rest Nb7f9988fc45843189bb6d04f52c6b85a
78 N64900b35db964a719496e745e4a482ab schema:isbn 978-3-540-73816-9
79 978-3-540-73817-6
80 schema:name Recent Advances in Constraints
81 rdf:type schema:Book
82 N75769a83afbc487394a20cbee03827bd rdf:first sg:person.014561740275.66
83 rdf:rest N1ab8fb622c824da5bb541f930d27ba85
84 Nae94c76e1a274fdb9ab306e3647e84d4 schema:familyName Fages
85 schema:givenName François
86 rdf:type schema:Person
87 Nb4337801dbe0459f8b6e611c9be3f63c schema:familyName Rossi
88 schema:givenName Francesca
89 rdf:type schema:Person
90 Nb7f9988fc45843189bb6d04f52c6b85a rdf:first N23dcb4ff475e404aaadefc21035325ea
91 rdf:rest Nd182720a9f71444ca757bb223772aafe
92 Nc444b5592c814ed8a559ba6f156b3318 schema:name Springer Nature
93 rdf:type schema:Organisation
94 Nd182720a9f71444ca757bb223772aafe rdf:first Nae94c76e1a274fdb9ab306e3647e84d4
95 rdf:rest N4febb7cb93c24ef1817c643f2c2b814f
96 Nd88299bbf8aa459b85a36356e3816d64 schema:name dimensions_id
97 schema:value pub.1029096534
98 rdf:type schema:PropertyValue
99 Ne92a5c3d83184ce8b6fcb260c1e74590 rdf:first sg:person.013750414271.15
100 rdf:rest rdf:nil
101 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
102 schema:name Mathematical Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
105 schema:name Pure Mathematics
106 rdf:type schema:DefinedTerm
107 sg:person.013371444706.47 schema:affiliation grid-institutes:grid.6582.9
108 schema:familyName Djelloul
109 schema:givenName Khalil
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013371444706.47
111 rdf:type schema:Person
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 sg:person.014561740275.66 schema:affiliation grid-institutes:grid.6582.9
118 schema:familyName Meister
119 schema:givenName Marc
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014561740275.66
121 rdf:type schema:Person
122 grid-institutes:grid.6582.9 schema:alternateName Fakultät für Ingenieurwissenschaften und Informatik, Universität Ulm, Germany
123 schema:name Fakultät für Ingenieurwissenschaften und Informatik, Universität Ulm, Germany
124 rdf:type schema:Organization
 




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


...