• DocumentCode
    2503723
  • Title

    Two EREW algorithms for parentheses matching

  • Author

    Prasad, Sushil ; Deo, Narsingh

  • Author_Institution
    Dept. of Math. & Comput. Sci., Georgia State Univ., Atlanta, GA, USA
  • fYear
    1991
  • fDate
    30 Apr-2 May 1991
  • Firstpage
    126
  • Lastpage
    131
  • Abstract
    The authors present two new parallel algorithms for matching parentheses on an exclusive-read exclusive-write parallel random-access machine (EREW PRAM). The first algorithm uses n processors and O(n) space, and requires O(log n) time to match n parentheses. The second algorithm is cost-optimal, and uses O(logn/n) processors and O(n log n ) space, and it requires O(log n) time. These algorithms are simpler and more elegant than the existing ones, and provide new insights into the parentheses matching problem
  • Keywords
    computational complexity; grammars; parallel algorithms; EREW PRAM; EREW algorithms; exclusive-read exclusive-write parallel random-access machine; parallel algorithms; parentheses matching; Binary trees; Computer science; Concurrent computing; Merging; Phase change random access memory; Pipeline processing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1991. Proceedings., Fifth International
  • Conference_Location
    Anaheim, CA
  • Print_ISBN
    0-8186-9167-0
  • Type

    conf

  • DOI
    10.1109/IPPS.1991.153767
  • Filename
    153767
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2503723