Cornell Math - MATH 788, Fall 2005

MATH 788: Applied Logic (Fall 2005)

Instructor: Bakhadyr Khoussainov

Meeting Time & Room

This term the course will be on Automatic Structures. It will be devoted to the study of structures that have presentations by automata (e.g. finite automata, tree automata, Buchi automata). Topics to be covered are:

  1. Characterization theorems for automatic structures. The main results here include characterization of automatic structures in terms of definability in fragments of arithmetic, in the additive group of reals, etc.
  2. The theory of automatic trees with an emphasis to automata-theoretic versions of Konig's lemma. Cantor Bendixson ranks of automatic trees.
  3. A characterization theorem (by Thomas) of finite automata presentable finitely generated groups. The theorem states that a f.g. group has a finite automata presentation iff it is residually abelian.
  4. A characterization of automatic Boolean algebras.
  5. Automatic linear orders. Cantor-Bendixson ranks of such orders.
  6. Sigma_1,1 -completeness of the isomorphism problem for automatic structures.
  7. Methods of proving non-automaticity. Applications to random graphs, universal partial orders.
  8. Intrinsic regular relations.
  9. Complexity of the satisfiability problem for automatic structures.