Annex 6: Habilitation thesis reader's report
Masaryk University Faculty
Field of Habilitation
Faculty of Science MU
Mathematics - Algebra and Number Theory
Applicant Affiliation Habilitation Thesis
Mgr. Ondfej Klima, Ph.D. Faculty of Science MU
Classifications of regular languages by equational properties of finite semigroups
Reader Affiliation
Benjamin Steinberg City College of New York
Report Text (as large as the reader deems necessary )
I think the habilitation thesis is an excellent piece of work and should be accepted. It combines several important papers of the author, which have had lasting impact. In my opinion the two strongest parts are giving a counterexample to the conjecture of Straubing on dot-depth 2 and completing the proof of join-irreduciblity for varieties of finite semigroups induced by varities of finite groups. But these are by no means the only important results. The results on complexity checking are also quite important.
Long ago Straubing conjectured that the second level of the monoidal dot-depth hierarchy should be the Malcev product of dot-depth 1 languages with semilattices. In fact, Pin and Weil made a more general conjecture that was disproved by Steinberg, but the original conjecture of Straubing was open for many years until it was disproved by Almeida and Klima in a brilliant piece of work.
Let H be a variety of finite groups. Then H will denote the variety of all finite semigroups whose subgroups belong to H. Margolis, Sapir and Weil used profinite techniques to prove that H was join irreducible whenever H was closed under semidirect product. Rhodes and Steinberg used Rees matrix semigroup constructions to prove that JH was join irreducible so long as H contained a non-nilpotent group. Almeida and Klima cleverly combined these two proof techniques to prove that H is always join irreducible. It should be mentioned that there bullet construction is quite old and was used by Allen and Rhodes in the synthesis theorem and by Rhodes in his theory of infinite iterated Rees matrix semigroups. Is also essentially used in a special case in the proof of Rhodes and Steinberg.
The section on biautomata is perhaps the least earth-shattering part of the thesis because this idea is essentially known in another context under another name. If M is a monoid and K is a field, then a representative function is a mapping f:M-> K such that the riaht KM-submodule of KAM aenerated bv f is finite dimensional.
In particular, if K is the two element field and M is the free monoid, then representative functions are the same things as characteristic functions of regular languages. In the subject of representative functions it is know that finite dimensionality of the left KM-module and the KM-KM-bimodule generated by f are equivalent to f being representative. Moreover they have an analogue of left and right quotients. Regular languages and Schutzenberger's theory of rational power series are special cases of this general theory and it is sort of known that the bimodule generated by f is the minimal bimodule recognizing it. Nonetheless, the new proof of Simon's theorem from this viewpoint is nice enough to make this section worthwhile.
Reader's questions to answer to defend the habilitation thesis (number of questions is upon reader's consideration)
1. Can you use the Krohn-Rhodes theorem to show that the only bullet idempotents are of the form H?
2. Do any of the new proofs of Simon's theorem help give insight into dot-depth 2? Conclusion
Ondfej Klima's habilitation thesis "Classifications of regular languages by equational properties of finite semigroups" does meet the standard requirements for habilitation thesis in the field of Mathematics - Algebra and Number Theory.
In New York on June 1, 2013...