Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Two nonlinear lower bounds for on-line computations
Dūris P., Galil Z., Paul W. (ed), Reischuk R. Information and Control60 (1-3):1-11,1984.Type:Article
Date Reviewed: Aug 1 1985

The following lower bounds for on-line computation are proved: (1) Simulating two-tape nondeterministic machines by one-tape machines requires &OHgr;(n log n) time. (2) Simulating k-tape (deterministic) machines by machines with k-pushdown stores requires &OHgr;(n log1/k+1) n) time.

--Authors’ Abstract

--Abstract recommended by J. Hartmanis, Ithaca, NY

Reviewer:  J. Hartmanis Review #: CR108986
Bookmark and Share
 
Bounded-Action Devices (F.1.1 ... )
 
 
Reducibility And Completeness (F.1.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Bounded-Action Devices": Date
Fairness and conspiracies
Best E. Information Processing Letters 18(4): 215-220, 1984. Type: Article
May 1 1985
Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe
Krause M., Meinel C., Waack S. Theoretical Computer Science 86(2): 267-275, 1991. Type: Article
Jul 1 1992
Probabilistic Turing machines and recursively enumerable Dedekind cuts
Chrobak M., Chlebus B. Information Processing Letters 19(4): 167-171, 1984. Type: Article
Jan 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy