| |
|
|
| |
| |
|
Date Reviewed |
|
| |
1 - 10 of 21
reviews
|
|
|
 |
|
|
|
|
Computability
Bridges D., Springer-Verlag New York, Inc., New York, NY, 1994. Type: Book (9780387941745)
As is pointed out in the preface, the intention of the book is “to provide mathematicians and mathematically literate computer scientists with a brief but rigorous introduction to a number of topics in the abstract theory of ...
|
Sep 1 1994 |
|
|
|
|
|
|
If not empty, NP−P is topologically large
Zimand M. Theoretical Computer Science 119(2): 293-310, 1993. Type: Article
Zimand proves that, in a combination of Cantor and superset topologies, the set NP−P, if not empty, is of the second (Baire) category, while NP-complete sets form a first-category class. These results are extended to differen...
|
Aug 1 1994 |
|
|
|
|
|
|
Unambiguity of circuits
Lange K. Theoretical Computer Science 107(1): 77-94, 1993. Type: Article
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] character...
|
May 1 1994 |
|
|
|
|
|
|
The membership problem in aperiodic transformation monoids
Beaudry M., McKenzie P., Thérien D. Journal of the ACM 39(3): 599-616, 1992. Type: Article
The computational complexity of the membership problem for a subset V of the class of all finite aperiodic monoids is studied. The results are the following. With one family of NP-hard exceptions whose exact status is still u...
|
Dec 1 1993 |
|
|
|
|
|
|
Time complexity of Boolean functions on CREW PRAMs
Kutylowski M. SIAM Journal on Computing 20(5): 824-853, 1991. Type: Article
A new method for estimating PRAM (parallel random access machine) complexity of Boolean functions is presented. Let CREW( f ) be the number of steps required by concurrent read exclusive write (CREW) PRAMs to comput...
|
May 1 1993 |
|
|
|
|
|
|
Computations over finite monoids and their test complexity
Becker B., Sparmann U. Theoretical Computer Science 84(2): 225-250, 1991. Type: Article
The authors consider the test pattern generation problem for circuits that compute expressions over free monoids. They study two computations, expression evaluation and parallel prefix computation. In both cases, the family of all fini...
|
Sep 1 1992 |
|
|
|
|
|
|
Lower bounds for algebraic computation trees with integer inputs
Yao A. (ed) SIAM Journal on Computing 20(4): 655-668, 1991. Type: Article
The problem of deciding whether x ∈ Z n is a member of a scale-invariant and rationally dispersed W ∈ &RR; n has complexity &OHgr; (
|
Jul 1 1992 |
|
|
|
|
|
|
An algorithm deciding functional equivalence in a new class of program schemes
Sabelfeld V. Theoretical Computer Science 71(2): 265-279, 1990. Type: Article
The equivalence of program schemes is undecidable, even for restricted classes of schemes. Early decidability results for classes of schemes were obtained by Ianov [1] and Bird [2]. The author proposes an algorithm deciding functional ...
|
Apr 1 1992 |
|
|
|
|
|
|
Communication and concurrency
Milner R., Prentice-Hall, Inc., Upper Saddle River, NJ, 1989. Type: Book (9780131150072)
This book offers a mathematical theory of communicating systems. The theory is not confined to the basic concepts of communication and concurrency, but applies to the general study of machines, architectures, programming methods, and l...
|
Jan 1 1990 |
|
|
|
|
|
|
Fast simulation of Turing machines by random access machines
Katajainen J., van Leeuwen J., Penttonen M. SIAM Journal on Computing 17(1): 77-88, 1988. Type: Article
The authors consider the problem of efficiently simulating Turing machines (TMs) with random access machines (RAMs). Their main results are that, under the logarithmic cost criterion, a RAM with no multiplication or division instructio...
|
Aug 1 1989 |
|
|
|
|
|
| |
|
|
| |
|
|
