From: Bhushan Mandhani (bhushan@cs.washington.edu)
Date: Wed Apr 28 2004 - 10:57:14 PDT
This paper, as the title suggests, describes what a crucial role logic
plays in computer science. It draws an analogy with the role of maths in
the natural sciences. In fact, logic is far more important in CS than it
is maths itself, where it is largely a fringe area.
It then goes on to describe the interaction between logic and complexity
theory. Clearly, a rich and interesting theory exists here. Complexity
classes are mapped to sentences in logic, with some specified expressive
power, so that each language in a class is described by a formula in the
corresponding logic. For example, NP is equivalent to second order
existential formulas, P to FOL with recursion, and so on. Overall, this
gives a new enlightening view of both logic and complexity.
Then it talks about databases, which are clearly one of the great
successes of the use of logic in CS. FOL is an appropriate and powerful
query language for relational data. What makes its use possible is that it
can be efficiently implemented using relational algebra. Individual
operations are efficiently done using indexes, and the algebra query
itself is optimized using rewriting rules. Finally, a language like SQL is
used for formulating these queries.
The paper goes on to further describe areas in which logic has been
successfully used. Thus, logic has many practical applications, in
addition to being a rich and interesting subject to study by itself.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 10:57:16 PDT