Parallelizing Union-Find in Constraint Handling Rules Using Confluence Analysis View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Thom Frühwirth

ABSTRACT

Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we investigate if a parallel implementation of this algorithm is also possible in CHR. The problem is hard for several reasons:- Up to now, no parallel computation model for CHR was defined.- Tarjan’s optimal union-find is known to be hard to parallelize.- The parallel code should be as close as possible to the sequential one.It turns out that confluence analysis of the sequential implementation gives almost all the information needed to parallelize the union-find algorithm under a rather general parallel computation model for CHR. More... »

PAGES

113-127

Book

TITLE

Logic Programming

ISBN

978-3-540-29208-1
978-3-540-31947-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11562931_11

DOI

http://dx.doi.org/10.1007/11562931_11

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Faculty of Computer Science, University of Ulm, Germany", 
          "id": "http://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"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we investigate if a parallel implementation of this algorithm is also possible in CHR. The problem is hard for several reasons:- Up to now, no parallel computation model for CHR was defined.- Tarjan\u2019s optimal union-find is known to be hard to parallelize.- The parallel code should be as close as possible to the sequential one.It turns out that confluence analysis of the sequential implementation gives almost all the information needed to parallelize the union-find algorithm under a rather general parallel computation model for CHR.", 
    "editor": [
      {
        "familyName": "Gabbrielli", 
        "givenName": "Maurizio", 
        "type": "Person"
      }, 
      {
        "familyName": "Gupta", 
        "givenName": "Gopal", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11562931_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29208-1", 
        "978-3-540-31947-4"
      ], 
      "name": "Logic Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "union-find algorithm", 
      "parallel computation model", 
      "Constraint Handling Rules", 
      "Handling Rules", 
      "computation model", 
      "rule-based language", 
      "Union-Find", 
      "optimal time complexity", 
      "time complexity", 
      "sequential implementation", 
      "parallel code", 
      "parallel implementation", 
      "sequential one", 
      "confluence analysis", 
      "algorithm", 
      "implementation", 
      "rules", 
      "complexity", 
      "Tarjan", 
      "language", 
      "code", 
      "information", 
      "model", 
      "one", 
      "analysis", 
      "reasons", 
      "CHR", 
      "problem", 
      "logical concurrent committed-choice rule-based language", 
      "concurrent committed-choice rule-based language", 
      "committed-choice rule-based language", 
      "classical union-find algorithm", 
      "general parallel computation model", 
      "Parallelizing Union-Find"
    ], 
    "name": "Parallelizing Union-Find in Constraint Handling Rules Using Confluence Analysis", 
    "pagination": "113-127", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030053121"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11562931_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11562931_11", 
      "https://app.dimensions.ai/details/publication/pub.1030053121"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:56", 
    "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_121.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11562931_11"
  }
]
 

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/11562931_11'

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/11562931_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11562931_11'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11562931_11'


 

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

99 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11562931_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd245fe98b9cc4afb9326b028a5811ac8
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we investigate if a parallel implementation of this algorithm is also possible in CHR. The problem is hard for several reasons:- Up to now, no parallel computation model for CHR was defined.- Tarjan’s optimal union-find is known to be hard to parallelize.- The parallel code should be as close as possible to the sequential one.It turns out that confluence analysis of the sequential implementation gives almost all the information needed to parallelize the union-find algorithm under a rather general parallel computation model for CHR.
7 schema:editor N1e04ed32d09f4bfbb5cd81106178f465
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N2b8825236825405285efaff4e222a7a1
12 schema:keywords CHR
13 Constraint Handling Rules
14 Handling Rules
15 Parallelizing Union-Find
16 Tarjan
17 Union-Find
18 algorithm
19 analysis
20 classical union-find algorithm
21 code
22 committed-choice rule-based language
23 complexity
24 computation model
25 concurrent committed-choice rule-based language
26 confluence analysis
27 general parallel computation model
28 implementation
29 information
30 language
31 logical concurrent committed-choice rule-based language
32 model
33 one
34 optimal time complexity
35 parallel code
36 parallel computation model
37 parallel implementation
38 problem
39 reasons
40 rule-based language
41 rules
42 sequential implementation
43 sequential one
44 time complexity
45 union-find algorithm
46 schema:name Parallelizing Union-Find in Constraint Handling Rules Using Confluence Analysis
47 schema:pagination 113-127
48 schema:productId N41a509b22dfc416d8c2af233fccd17e3
49 N86fb55e33f234b88994286c6e2943670
50 schema:publisher N3be7932ffe1340a98c897c0205751e31
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030053121
52 https://doi.org/10.1007/11562931_11
53 schema:sdDatePublished 2021-12-01T19:56
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N0bdd1f3affdd4aa6aacef8e463ad378f
56 schema:url https://doi.org/10.1007/11562931_11
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N0bdd1f3affdd4aa6aacef8e463ad378f schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N1e04ed32d09f4bfbb5cd81106178f465 rdf:first N82229691a7c5490a9a675808544d49c4
63 rdf:rest N29ca0c10dfa8445caa9ae6c882d4c2f0
64 N29ca0c10dfa8445caa9ae6c882d4c2f0 rdf:first N8ca0ae366dbe4d45b4249389e9f25ce3
65 rdf:rest rdf:nil
66 N2b8825236825405285efaff4e222a7a1 schema:isbn 978-3-540-29208-1
67 978-3-540-31947-4
68 schema:name Logic Programming
69 rdf:type schema:Book
70 N3be7932ffe1340a98c897c0205751e31 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N41a509b22dfc416d8c2af233fccd17e3 schema:name doi
73 schema:value 10.1007/11562931_11
74 rdf:type schema:PropertyValue
75 N82229691a7c5490a9a675808544d49c4 schema:familyName Gabbrielli
76 schema:givenName Maurizio
77 rdf:type schema:Person
78 N86fb55e33f234b88994286c6e2943670 schema:name dimensions_id
79 schema:value pub.1030053121
80 rdf:type schema:PropertyValue
81 N8ca0ae366dbe4d45b4249389e9f25ce3 schema:familyName Gupta
82 schema:givenName Gopal
83 rdf:type schema:Person
84 Nd245fe98b9cc4afb9326b028a5811ac8 rdf:first sg:person.013750414271.15
85 rdf:rest rdf:nil
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.013750414271.15 schema:affiliation grid-institutes:grid.6582.9
93 schema:familyName Frühwirth
94 schema:givenName Thom
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013750414271.15
96 rdf:type schema:Person
97 grid-institutes:grid.6582.9 schema:alternateName Faculty of Computer Science, University of Ulm, Germany
98 schema:name Faculty of Computer Science, University of Ulm, Germany
99 rdf:type schema:Organization
 




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


...