Techniques in my Proof that Complexity is Decidable for Finite Automata and Semigroups.
by
John Rhodes
University of California, Berkeley

I use five or six main techniques to prove that complexity, c, is decidable. I will discuss three of these, and try to give the listener some idea of the proof.

The first technique I'll discuss is McCammond automata and the McCammond expansion, from our joint paper, "Geometric Semigroup Theory."

Second, I will discuss the delay k-expansion for each positive integer k of a finite automata, and then the combinatorics involved in applying this expansion an infinite number of times to the relevant defining relational morphisms, using the decomposition technique of breaking into maximal proper surmorphisms (MPS).

Finally, I will provide some indication of the proof. Some pictures will be drawn during the lecture.

Date received: June 12, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-44.