Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Space-efficient deterministic simulation of probabilistic automata
Macarie I. SIAM Journal on Computing27 (2):448-465,1998.Type:Article
Date Reviewed: Mar 1 1999

Elegant number-theoretic techniques are used to answer a very natural, decades-old open problem regarding probabilistic finite automata. The author shows that the languages recognized by probabilistic finite automata can be recognized in deterministic logarithmic space. (The result is generalized and extended to probabilistic automata with nonconstant but very slow-growing space bounds.)

Like most previous space-efficient simulations of probabilistic finite automata, Macarie’s work makes heavy use of the Chinese remainder theorem. One of the main technical contributions is a nice construction of an algorithm to determine, given two numbers x and y expressed in Chinese remainder representation, whether x < y.

Some fundamental questions about the complexity of probabilistic finite automata still remain open. One deserving special mention is the question of whether these machines can be simulated by bounded fan-in Boolean circuits of logarithmic depth. (That is, are the languages accepted by probabilistic finite automata in the complexity class NC1?)

Reviewer:  Eric Allender Review #: CR121908 (9903-0185)
Bookmark and Share
 
Bounded-Action Devices (F.1.1 ... )
 
 
Matrix Inversion (G.1.3 ... )
 
 
Stochastic Processes (G.3 ... )
 
 
Complexity Measures And Classes (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
Two nonlinear lower bounds for on-line computations
Dūris P., Galil Z., Paul W. (ed), Reischuk R. Information and Control 60(1-3): 1-11, 1984. Type: Article
Aug 1 1985
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