Parallel algorithms for parenthesis matching and generation of random balanced sequences of parentheses View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1988

AUTHORS

Dilip Sarkar , Narsingh Deo

ABSTRACT

Parallel parenthesis-matching algorithm has in the past been used to design parallel algorithms for generation of computation tree forms and parsing. In this paper we present a parallel parenthesis-matching algorithm. A variant of binary search tree is constructed in parallel. The search tree is used to find the matching of each parenthesis. The algorithm takes O(log n) time on a (n / log n)-processor CREW-PRAM. We also present an O(log n)-time parallel algorithm for generation of random sequences of parentheses. These two algorithms can be used to design an O(log n)-time parallel algorithm for generation of a class of random permutations. More... »

PAGES

970-984

Book

TITLE

Supercomputing

ISBN

978-3-540-18991-6
978-3-540-38888-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-18991-2_57

DOI

http://dx.doi.org/10.1007/3-540-18991-2_57

DIMENSIONS

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


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": "University of Central Florida", 
          "id": "https://www.grid.ac/institutes/grid.170430.1", 
          "name": [
            "Department of Computer Science, University of Central Florida, 32816\u00a0Orlando, FL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sarkar", 
        "givenName": "Dilip", 
        "id": "sg:person.012464214547.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012464214547.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Central Florida", 
          "id": "https://www.grid.ac/institutes/grid.170430.1", 
          "name": [
            "Department of Computer Science, University of Central Florida, 32816\u00a0Orlando, FL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Deo", 
        "givenName": "Narsingh", 
        "id": "sg:person.010274011142.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1988", 
    "datePublishedReg": "1988-01-01", 
    "description": "Parallel parenthesis-matching algorithm has in the past been used to design parallel algorithms for generation of computation tree forms and parsing. In this paper we present a parallel parenthesis-matching algorithm. A variant of binary search tree is constructed in parallel. The search tree is used to find the matching of each parenthesis. The algorithm takes O(log n) time on a (n / log n)-processor CREW-PRAM. We also present an O(log n)-time parallel algorithm for generation of random sequences of parentheses. These two algorithms can be used to design an O(log n)-time parallel algorithm for generation of a class of random permutations.", 
    "editor": [
      {
        "familyName": "Houstis", 
        "givenName": "E. N.", 
        "type": "Person"
      }, 
      {
        "familyName": "Papatheodorou", 
        "givenName": "T. S.", 
        "type": "Person"
      }, 
      {
        "familyName": "Polychronopoulos", 
        "givenName": "C. D.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-18991-2_57", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-18991-6", 
        "978-3-540-38888-3"
      ], 
      "name": "Supercomputing", 
      "type": "Book"
    }, 
    "name": "Parallel algorithms for parenthesis matching and generation of random balanced sequences of parentheses", 
    "pagination": "970-984", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-18991-2_57"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "855dd4af9756cdfd9db4e735b811013b3e3e59417ec62e69a8dafc45b72b8161"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027996490"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-18991-2_57", 
      "https://app.dimensions.ai/details/publication/pub.1027996490"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T22:42", 
    "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_8695_00000048.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-18991-2_57"
  }
]
 

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/3-540-18991-2_57'

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/3-540-18991-2_57'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-18991-2_57'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-18991-2_57'


 

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

82 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-18991-2_57 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1153f0fcde694e8fae98efb61e2b1b30
4 schema:datePublished 1988
5 schema:datePublishedReg 1988-01-01
6 schema:description Parallel parenthesis-matching algorithm has in the past been used to design parallel algorithms for generation of computation tree forms and parsing. In this paper we present a parallel parenthesis-matching algorithm. A variant of binary search tree is constructed in parallel. The search tree is used to find the matching of each parenthesis. The algorithm takes O(log n) time on a (n / log n)-processor CREW-PRAM. We also present an O(log n)-time parallel algorithm for generation of random sequences of parentheses. These two algorithms can be used to design an O(log n)-time parallel algorithm for generation of a class of random permutations.
7 schema:editor N8c40286f26eb4ce69b2a76813b433f7c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nd9e334d94e0b4fa391e418ddb272912c
12 schema:name Parallel algorithms for parenthesis matching and generation of random balanced sequences of parentheses
13 schema:pagination 970-984
14 schema:productId N259f49c4ad624338a7f7b9bf093c636f
15 N4dcc877d217d43ac8d5ec8065b33243f
16 N544dda4d7e0242eb9c1bbe56708c06cb
17 schema:publisher N64d123469d654575aabf631e83ca53c0
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027996490
19 https://doi.org/10.1007/3-540-18991-2_57
20 schema:sdDatePublished 2019-04-15T22:42
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nc23e98fcece249c68e38ac1b2553f3ca
23 schema:url http://link.springer.com/10.1007/3-540-18991-2_57
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N0a5520bfdf63438eb3b406a14fdc4311 schema:familyName Polychronopoulos
28 schema:givenName C. D.
29 rdf:type schema:Person
30 N1153f0fcde694e8fae98efb61e2b1b30 rdf:first sg:person.012464214547.63
31 rdf:rest N3e1200dbf574477383ab8896ac8986b4
32 N2498d51997464cb2877abf11c3f9b638 rdf:first N0a5520bfdf63438eb3b406a14fdc4311
33 rdf:rest rdf:nil
34 N259f49c4ad624338a7f7b9bf093c636f schema:name dimensions_id
35 schema:value pub.1027996490
36 rdf:type schema:PropertyValue
37 N3e1200dbf574477383ab8896ac8986b4 rdf:first sg:person.010274011142.47
38 rdf:rest rdf:nil
39 N4dcc877d217d43ac8d5ec8065b33243f schema:name readcube_id
40 schema:value 855dd4af9756cdfd9db4e735b811013b3e3e59417ec62e69a8dafc45b72b8161
41 rdf:type schema:PropertyValue
42 N544dda4d7e0242eb9c1bbe56708c06cb schema:name doi
43 schema:value 10.1007/3-540-18991-2_57
44 rdf:type schema:PropertyValue
45 N64d123469d654575aabf631e83ca53c0 schema:location Berlin, Heidelberg
46 schema:name Springer Berlin Heidelberg
47 rdf:type schema:Organisation
48 N853ceda91136488e8e355875de62cb61 schema:familyName Papatheodorou
49 schema:givenName T. S.
50 rdf:type schema:Person
51 N8c40286f26eb4ce69b2a76813b433f7c rdf:first Ncc63b7c317ea439db3a2f9f139f92e2a
52 rdf:rest Nbc7dfaee04984e9cad7b7066f8ff5418
53 Nbc7dfaee04984e9cad7b7066f8ff5418 rdf:first N853ceda91136488e8e355875de62cb61
54 rdf:rest N2498d51997464cb2877abf11c3f9b638
55 Nc23e98fcece249c68e38ac1b2553f3ca schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 Ncc63b7c317ea439db3a2f9f139f92e2a schema:familyName Houstis
58 schema:givenName E. N.
59 rdf:type schema:Person
60 Nd9e334d94e0b4fa391e418ddb272912c schema:isbn 978-3-540-18991-6
61 978-3-540-38888-3
62 schema:name Supercomputing
63 rdf:type schema:Book
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
68 schema:name Computation Theory and Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
71 schema:familyName Deo
72 schema:givenName Narsingh
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
74 rdf:type schema:Person
75 sg:person.012464214547.63 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
76 schema:familyName Sarkar
77 schema:givenName Dilip
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012464214547.63
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.170430.1 schema:alternateName University of Central Florida
81 schema:name Department of Computer Science, University of Central Florida, 32816 Orlando, FL
82 rdf:type schema:Organization
 




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


...