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 Kh'ma, Ph.D. Faculty of Science MU
Classifications of regular languages by equational properties of finite semigroups
Reader Affiliation
Pascal Weil
CNRS and Universite de Bordeaux (LaBRI)
Report Text (as large as the reader deems necessary )
The habilitation manuscript submitted by Ondfej Klima is centered on the general problem of classifying regular languages using equational properties of finite semigroups: this puts his research work on the frontier between theoretical computer science and mathematics.
I will therefore start with a word on the importance of this classification problem, which forms one of the most important branches of the theory of finite state automata, a cornerstone of computer science and the theory of computation. Finite state automata (and the languages they recognize, namely regular languages) were identified as the simplest model of computation already in the late 1950s (Chomsky hierarchy), which gives them a special role in the theory of computation. In addition, they are universally present in all applications of computer science, from text processing to the logical specification and the synthesis of controllers for complex systems. Hence the importance of a detailed classification of regular languages, both theoretically - as a measure of complexity for automata and computations (those computations that can be performed by finite state automata), and practically - since this classification has strong consequences on the complexity of algorithms using these languages.
These considerations meet algebra as it turns out that finite state automata can be also considered as a privileged tool to investigate and represent finite semigroups and monoids. And the natural universal algebraic classification of semigroups can be very fruitfully applied to the classification of regular languages. This classification captures in particular many natural combinatorially or logically defined classes of languages: the language of algebra, through the through the theory of varieties and pseudovarieties, or through the equational theory of semigroups, then provides a unique tool to express properties of classes of languages and, in good cases, to decide these properties.
This provides the framework within which Ondfej Kh'ma has developed his work, and to which he has made a number of very significant contributions. In this respect, his choice of articles, to be included as part of the habilitation manuscript, is quite tasteful. This collection of papers also gives an important indication on Ondfej Klfma's mathematical ability: indeed it shows that he has been able to collaborate fruitfully not only in his immediate environment at Masaryk University but also with world-class mathematicians in Portugal and in Canada, who are internationally recognized as specialists in the field. I take this to be a very good indicator
of Ondfej Klima's scientific autonomy and mathematical inventiveness.
I would like to further comment on two streams of the research presented here, which I find particularly significant, possibly because they are closely related to research work with which I was personally involved. A common feature of both these streams is how Ondfej Klima (with his co-authors) manages to bring new ideas in the discussion of old questions, resulting in substantial progress.
- In the investigation of the lower levels of the concatenation hierarchies, progress had been extremely slow in the past 10 years or so (the main problem, open for 45 years now, is the decidability of the different levels of these hierarchies). And it would have seemed that we had reached full understanding of the very first level of the Straubing-Therien hierarchy, namely the class of piecewise testable languages. Yet Ondfej Klima and co-authors brought a new proof of the founding result on these languages (their algebraic characterization in terms of J-trivial semigroups), which is quite different from previous proofs.
- Ondfej Klima's (and co-author's) results on the irreducibility of a vast class of pseudovarieties are even more impressive. The statement of their theorem (Theorem 8 in the manuscript) is similar to that of results of 1998 (Margolis, Sapir, Weil) and 2004 (Rhodes, Steinberg), but they manage to lift all the restrictive hypotheses that were used in the proofs of the earlier results. This is done by the introduction of a new operation, which may prove very useful in the future and for other purposes. In fact, other authors (esp. Diekert) independently discovered this operation, - or re-discovered it, since it can also be derived from early papers by Rhodes -, and this is further indication of the relevance of this operation.
Another very noteworthy work by Ondfej Klima regards the complexity of checking identities in finite semigroups. This is a somewhat under-studied, yet very important problem — if we are going to argue in favor of using algebraic methods to solve language-theoretic problems (which I would gladly do). The results presented in the habilitation manuscript bring some clarity and a number of new results to that area. It would be interesting to see whether the approach used there can be extended to handle the new trends in the equational approach, as found in recent work by Gehrke, Grigorieff and Pin. This may be a promising research direction.
To conclude, Ondfej Klima presents a very substantial list of publications, many of which appeared in highly respected journals (e.g. the Intern. J. Algebra and Computation, Theory of Computing Systems, Discrete Mathematics or RAIRO-Theoretical Informatics and Applications). The work presented in the manuscript and the whole of Ondfej Klima's scientific production are undoubtedly of the right caliber to earn him his habilitation degree.
Reader's questions to answer to defend the habilitation thesis (number of questions is upon reader's consideration)
1.
2.
Ondfej Klima's habilitation thesis "Classifications of regular languages by equational properties of finite semigroups" does - doco not meet the standard requirements for habilitation thesis in the field of Mathematics - Algebra and Number Theory.
In   Bordeaux, on April 28,2013 signature