Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Unambiguity of circuits
Lange K. Theoretical Computer Science107 (1):77-94,1993.Type:Article
Date Reviewed: May 1 1994

The author considers the concept of unambiguity of circuits and studies several classes of unambiguous circuit families within the NC-hierarchy. In particular, he answers an open question from L. Stockmeyer and C. Vishkin [1] characterizing CREW-PRAMs in terms of unambiguous circuits: CREW-PRAM( log k n )= UnambACk.
Reviewer:  C. Calude Review #: CR117726
1) Stockmeyer, L. and Vishkin, C. Simulation of random access machines by circuits. SIAM J. Comput. 13 (1984), 409–422.
Bookmark and Share
 
Complexity Hierarchies (F.1.3 ... )
 
 
Automata (F.1.1 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
 
Path And Circuit Problems (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Complexity Hierarchies": Date
Bounded queries to SAT and the Boolean hierarchy
Beigel R. (ed) Theoretical Computer Science 84(2): 199-223, 1991. Type: Article		 Oct 1 1992
Minimal degrees for polynomial reducibilities
Homer S. (ed) Journal of the ACM 34(2): 480-491, 1987. Type: Article		 Nov 1 1987
Some hierarchies for the communication complexity measures of cooperating grammar systems
Hromkovič J., Kari J., Kari L. Theoretical Computer Science 127(1): 123-147, 1994. Type: Article		 Dec 1 1995
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