[Colloquium] University of Chicago Logic Seminar on 11/5/03

[Margery Ishmael]

Begin forwarded message:

> 	THE UNIVERSITY OF CHICAGO LOGIC SEMINAR ANNOUNCEMENT
>
> TIME:  Wednesday, November 5, 2003   2:30-4:00pm
>
> ROOM: Ryerson 251
>
> SPEAKER:  Bakh Khoussainov
> 	  Dept. of Computer Science
>  	  University of Auckland, New Zealand
>
> TITLE: Automatic Structures
>
> ABSTRACT:
>
> In this talk we introduce the notion of automatic structure.
> Informally, a structure is automatic if its atomic diagram can be
> recognized by finite automata. A foundational result obtained in 1995 
> by
> Nerode and the speaker states that the first order theory of any
> automatic structure is decidable. Thus, automatic structures are
> generic examples of decidable structures.  We provide many examples,
> and then investigate automatic linear orders and trees and explain why
> Cantor-Bendixson ranks of these structures are finite. We also outline
> why typical structures obtained via Frasse limits (such as random
> graphs, universal partial orders, atomless Boolean algebras) are not
> automatic though their theories are decidable. These observations
> suggest that there could be a way to describe automatic
> structures. However, we show that the isomorphism problem for
> automatic structures is Sigma_1^1-complete.
>
>
> NOTE: For current information on the logic seminars see the web site:
>
> www.cs.uchicago.edu/~soare/Seminars/
>
>