[an error occurred while processing this directive]
An error occured whilst processing this directive
Fast exhaustive search over infinite search spaces.
University of Birmingham
4pm Tuesday 5th September 2006
Room 2511, JCMB, King's Buildings
Abstract
It is known that there are infinite sets that admit exhaustive search
in finite time. The aim of this talk is to (1) make this surprising
fact available to a more general audience, (2) develop new results
about the nature of mechanically exhaustible sets, and (3) perform
first steps about the efficiency of exhaustive search over infinite
sets. Regarding (2), we show that exhaustible sets are closed under
computable images and finite and countable products, giving meaningful
examples, and, regarding (3), we discuss instances of exhaustive
searches that defy intuition not only for being over infinite sets,
but also for being faster than one would expect, briefly indicating
what is behind this unexpected behaviour. We also indicate potential
applications to automatic program verification and model checking.
An error occured whilst processing this directive