##### Department of Mathematics,

University of California San Diego

****************************

### Colloquium

## Mia Minnes

#### Cornell University

## Automatic structures: at the interface of classical and feasible mathematics

##### Abstract:

Finite state automata are Turing machines with fixed finite bounds on resource use. Automata lend themselves well to real-time computations and efficient algorithms. Therefore, there is a long tradition of studying that part of mathematics which can be represented by automata. This talk will give a survey of this research. In particular, we discuss three major themes: how complicated can automatic structures be? can they be naturally described? how efficient are the associated algorithms? Examples include Thurston's automatic groups associated with 3-manifolds and automatic structures associated to model checking and program verification in computer science.

Host: Bruce Driver

### April 24, 2008

### 4:00 PM

### AP&M 6402

****************************