LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Gibbons, Alan (Alan M.); Rytter, Wojciech
Publisher: University of Warwick. Department of Computer Science
Languages: English
Types: Other
Subjects: QA76
We describe a deterministic parallel algorithm to compute algebraic expressions in log n time using n/log(n) processors on a parallel random access machine without write confilects (P-RAM) with no free preprocessing. This improves the result of Miller and Reif (1985), who described an optimal parallel randomized algorithm. Our algorithm can be used to construct an optimal parallel algorithm for the recognition of two nontrivial subclasses of context-free languages: bracket and input-driven languages. These languages are the most complicated context-free languages known to be recognizable in deterministic logarithmic space. This strengthens the result of Matheyses and Fiduccia (1982), who constructed an almost optimal parallel algorithm for Dyck languages, since Dyck languages are a proper subclass of input-driven languages.\ud \ud Using our algorithm we show also that preorder and postorder numberings of the nodes of a tree can be computed by optimal parallel algorithms.
  • No references.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article