| |
|
|
| |
| |
|
Date Reviewed |
|
| |
1 - 10 of 22
reviews
|
|
|
 |
|
|
|
|
Natural computing: DNA, quantum bits, and the future of smart machines
Lazere C., Shasha D., W. W. Norton&Company, New York, NY, 2010. 288 pp. Type: Book (978-0-393336-83-2), Reviews: (3 of 3)
There are many possible approaches to natural computing--computing inspired by nature--and Lazere and Shasha’s new book gives a good overview of all of them. Using the successful formula of their previous bo...
|
Oct 4 2010 |
|
|
|
|
|
|
Deciding whether the frontier of a regular tree is scattered
Bloom S., Ésik Z. Fundamenta Informaticae 55(1): 1-21, 2003. Type: Article
Consider a finite alphabet &Sgr; and a finite set X of variables. Then we can consider equations of the form x = u, where x ∈ X...
|
Oct 29 2003 |
|
|
|
|
|
|
Computable analysis: an introduction
Weihrauch K., Springer-Verlag New York, Inc., Secaucus, NJ, 2000. 288 pp. Type: Book (9783540668176)
The type-2 theory of effectivity (TTE) is a computability theory, based on Turing machines with write-only output tapes, that extends standard computability theory on finite strings to infinite strings. These infinite strings can be us...
|
Sep 1 2001 |
|
|
|
|
|
|
Computability and complexity theory
Homer S., Selman A., Springer-Verlag New York, Inc., New York, NY, 2001. 194 pp. Type: Book (9780387950556)
The difference between this new introductory graduate textbook in theoretical computer science and other texts is that the authors have chosen to concentrate on computability theory and computational complexity theory. They motivate th...
|
Jul 1 2001 |
|
|
|
|
|
|
Computability (2nd ed.): computable functions, logic, and the foundations of mathematics
Epstein R., Carnielli W., Wadsworth Publ. Co., Belmont, CA, 2000. 337 pp. Type: Book (9780534546441)
The authors introduce computability theory from a philosophical perspective (after all, the theory was developed before there were any computers). From a purely mathematical point of view, there is not much remarkable about the treatme...
|
Jul 1 2000 |
|
|
|
|
|
|
Locality of order-invariant first-order formulas
Grohe M., Schwentick T. ACM Transactions on Computational Logic 1(1): 112-130, 2000. Type: Article
A famous theorem by Gaifman says that first-order logic can express only local properties of structures, in the sense that the truth of a first-order formula in an element (or tuple of elements) of some structure depends only on a cert...
|
Jun 1 2000 |
|
|
|
|
|
|
Existential second-order logic over strings
Eiter T., Gottlob G., Gurevich Y. Journal of the ACM 47(1): 77-131, 2000. Type: Article
Strings over a finite alphabet can be naturally represented as structures in the sense of mathematical logic. Indeed, for a string a1 ... an, we have a finite structure with n...
|
May 1 2000 |
|
|
|
|
|
|
Complexity and expressive power of deterministic semantics for DATALOG
Greco S., Saccá D. Information and Computation 153(1): 81-98, 1999. Type: Article
Logic programs without function symbols are known as Datalog programs (with negation, but this qualification will be understood in what follows). A Datalog program, viewed as a logic formula, may have many models. Various special kinds...
|
Oct 1 1999 |
|
|
|
|
|
|
Expressive power and complexity of partial models for disjunctive deductive databases
Eiter T., Leone N., Saccá D. Theoretical Computer Science 206(1/2): 181-218, 1998. Type: Article
Deductive databases are an approach to database query languages inwhich a query to a database is represented by a first-order formulathat, in addition to the names of the database relations, can alsomention additional relation names, c...
|
Jun 1 1999 |
|
|
|
|
|
|
Completeness and non-completeness results with respect to read-once projections
Bollig B., Wegener I. Information and Computation 143(1): 24-33, 1998. Type: Article
Representations of Boolean functions using restricted types of binary decision diagrams are popular in automated verification. This paper is concerned with reductions among computational problems that are appropriate for these kinds of...
|
Jun 1 1999 |
|
|
|
|
|
| |
|
|
| |
|
|
