|
|
|
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:
- 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.
- The theory of automatic trees with an emphasis to automata-theoretic
versions of Konig's lemma. Cantor Bendixson ranks of automatic trees.
- 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.
- A characterization of automatic Boolean algebras.
- Automatic linear orders. Cantor-Bendixson ranks of such orders.
- Sigma_1,1 -completeness of the isomorphism problem for automatic
structures.
- Methods of proving non-automaticity. Applications to random graphs,
universal partial orders.
- Intrinsic regular relations.
- Complexity of the satisfiability problem for automatic structures.
Last modified:
March 31, 2005
|
