From: Neva Cherniavsky (nchernia@cs.washington.edu)
Date: Wed Apr 28 2004 - 12:08:27 PDT
This paper describes how first order logic has impacted computer science,
in the same sense that mathematics has impacted the physical sciences;
namely, that logic is the "right" language for computer science. The
authors go on to list the ways in which logic applies to various fields,
and we read about the impact on computational complexity theory and on
databases.
I found the first very interesting; as a theory person, I'm surprised I've
never been introduced to these connections before. I'd particularly like
to know more about how P = PSPACE in FOL.
The second section was on databases and how FOL can be used as a database
query language. FOL helps in two areas: speeding up the queries and
allowing for massive parallelism. I find the main beauty of databases to
be this intimate connection between logic and queries. In many
application areas of computer science, solutions seem "hacked"; with
databases, the introduction of theory at the very beginning of the field
means the solutions are theoretically sound and provable.
This archive was generated by hypermail 2.1.6 : Wed Apr 28 2004 - 12:11:36 PDT