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
Mikhail Volkov
Ural Federal University, 62000 Ekaterinburg, Russia
Report Text (as large as the reader deems necessary )
The thesis comprises 10 research papers by the author (8 of them are joint work: three with Jorge Almeida, four with Libor Polák, and one with Denis Thérien and Pascal Tesson). Besides that, the thesis contains a nicely written overview of the papers which paces them in a proper perspective and a complete list of the author's publications.
8 of the papers included in the thesis have appeared in competitive and authoritative international journals in algebra, computer science and discrete mathematics: "Discrete Mathematics", "Discrete Mathematics and Theoretical Computer Science", "Information Processing Letters", "International Journal of Algebra and Computation", "International Journal of Foundations of Computer Science", "RAIRO Theoretical Informatics and Applications", "Semigroup Forum", "Theory of Computing Systems". One paper is submitted to a (non-specified) journal and yet another one is published in a conference volume from the renowned series "Lecture Notes in Computer Science". All the papers in the thesis meet the standards of a quality scientific publication; at least five of them can be even qualified as outstanding. These five are:
■ "Piecewise testable languages via combinatorics on words" [1],
■ "On biautomata" [2],
■ "A counterexample to a conjecture concerning concatenation hierarchies" [4],
■ "New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages" [5],
■ "Complexity issues of checking identities in finite monoids" [9].
The paper [1] is relatively short but it presents a new, original proof of Simon's celebrated theorem on piecewise testable languages. The author's construction is simple and elegant so that it certainly guarantees itself a place in the future textbooks and monographs in the area. I have already used the author's proof in lectures on the algebraic theory of regular languages for master students at my university, and I know some recent papers by other authors where the techniques invented in [1] are successfully applied in some other context.
The paper [2] (joint with Libor Polák) presents very deep and technically involved study of a new concept of a biautomaton which sheds new light on some classical aspects of the theory of regular languages. This concept clearly deserves further investigations.
The papers [4] and [5] are related to one of the most longstanding open problems in the regular language theory: the decidability of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages. The area was very popular in the 1990s but has stagnated since then and the resources of all existing approaches appeared to be exhausted. The author and Jorge Almeida have found some new ideas which allowed them to
well-known conjecture in the area and to establish a new decidable upper bound ^5 the second level in the concatenation hierarchy.
The paper [9] establishes very interesting connections between finite semigroup theory and computational complexity and presents a minimum example of a finite semigroup whose identity checking problem is co-NP-complete.
In his papers (not only in the ones included in the present thesis) the author shows a strong research potential, a deep knowledge and a good skill in semigroup theory, language and automata theory, and computational complexity. The way he presents his results also deserves a word of appreciation: he takes care of motivating the results, clearly states his goals, and is accurate and precise. His proofs supply enough detail but are concise and his language is always clear and adequate. Summarizing I can say that:
■ the thesis contains several novel scientific results of high level presented in a very good style;
■ the thesis clearly demonstrates that Dr. Klima is both a talented scientist and a mature scientific writer;
■ altogether, the thesis proves in a very convincing way that Dr. Klima masters the science of mathematics and is able to further promote it.
I strongly recommend the thesis be accepted.
Reader's questions to answer to defend the habilitation thesis (number of questions is upon reader's consideration)
1. What do you think, which further classes of regular languages can be nicely characterized via biautomata? In particular, do you expect that the concept can be efficiently used beyond the class of star-free languages?
2. What does the word "Slupste" mean in the bibliographic data for the reference [4] in the paper [10] (see page 183 of the thesis)?
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 Ekaterinburg on May 25th, 2013
signature