Research Seminar - May 21, 1999

Abstract

The various formal logics for temporal reasoning have many applications in Computer Science, AI, philosophy and natural language understanding. Much current research in the area is directed to finding efficient procedures for deciding whether a formula is a validity in one of these logics. However, for many of the logics it is not even known whether such procedures exist.

In this talk, I will introduce some of the basic concepts and uses of temporal logic and try to sketch how a couple of powerful techniques are being used to answer the decidability question. In particular, mathematical tiling problems can show undecidability and mosaics can show decidability.