File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Optimal EREW parallel algorithm for parenthesis matching

TitleOptimal EREW parallel algorithm for parenthesis matching
Authors
Tsang, Wai WanLam, Tak WChin, Francis YL
Issue Date1989
Citation
Proceedings Of The International Conference On Parallel Processing, 1989, v. 3, p. 185-192 How to Cite?
AbstractParenthesis matching is an important step in the construction of computation tree form and parsing. A new parallel algorithm is presented for matching a string of n parentheses in O(log n) time using n/log n processors on an exclusive-read, exclusive-write parallel random-access machine (EREW PRAM). The previously best-known method requires O(log2 n) time and n/log n processors on an EREW PRAM or a concurrent-read, exclusive-write PRAM for O(log n) time complexity.
Persistent Identifierhttp://hdl.handle.net/10722/151789
ISSN
0190-3918
2020 SCImago Journal Rankings: 0.269

 

DC FieldValueLanguage
dc.contributor.authorTsang, Wai Wanen_US
dc.contributor.authorLam, Tak Wen_US
dc.contributor.authorChin, Francis YLen_US
dc.date.accessioned2012-06-26T06:29:32Z-
dc.date.available2012-06-26T06:29:32Z-
dc.date.issued1989en_US
dc.identifier.citationProceedings Of The International Conference On Parallel Processing, 1989, v. 3, p. 185-192en_US
dc.identifier.issn0190-3918en_US
dc.identifier.urihttp://hdl.handle.net/10722/151789-
dc.description.abstractParenthesis matching is an important step in the construction of computation tree form and parsing. A new parallel algorithm is presented for matching a string of n parentheses in O(log n) time using n/log n processors on an exclusive-read, exclusive-write parallel random-access machine (EREW PRAM). The previously best-known method requires O(log2 n) time and n/log n processors on an EREW PRAM or a concurrent-read, exclusive-write PRAM for O(log n) time complexity.en_US
dc.languageengen_US
dc.relation.ispartofProceedings of the International Conference on Parallel Processingen_US
dc.titleOptimal EREW parallel algorithm for parenthesis matchingen_US
dc.typeConference_Paperen_US
dc.identifier.emailTsang, Wai Wan:tsang@cs.hku.hken_US
dc.identifier.emailLam, Tak W:twlam@cs.hku.hken_US
dc.identifier.emailChin, Francis YL:chin@cs.hku.hken_US
dc.identifier.authorityTsang, Wai Wan=rp00179en_US
dc.identifier.authorityLam, Tak W=rp00135en_US
dc.identifier.authorityChin, Francis YL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0024943797en_US
dc.identifier.volume3en_US
dc.identifier.spage185en_US
dc.identifier.epage192en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridTsang, Wai Wan=7201558521en_US
dc.identifier.scopusauthoridLam, Tak W=7202523165en_US
dc.identifier.scopusauthoridChin, Francis YL=7005101915en_US
dc.identifier.issnl0190-3918-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats