From: Atri Rudra (atri@cs.washington.edu)
Date: Tue Apr 27 2004 - 16:14:35 PDT
On the Unusual Effectiveness of Logic in Computer Science
----------------------------------------------------------
Halpern et. al.
This paper outlines how logic has percolated through Computer Science.
Section 2 discusses descriptive complexity classes and how logic can be
used to re-formulate the classic computational complexity classes. It is
interesting how this connection is generally not dealt with in much
detailin complexity courses (maybe because thinking in terms of computation is
easier).
Section 3 briefly outlines why first order logic and relational algebra
have made (relational) databases what they are today. The two most
important points are the fact that relational algebra make query
computations more efficient and that first order queries can in theory be
fully parallelized. The latter point is something which I had not
thought of (maybe because we are used to databases being real object
rather than just theoretical constructs ?)
This archive was generated by hypermail 2.1.6 : Tue Apr 27 2004 - 16:14:37 PDT