Práce byla odevzdána s domluveným týdenním odkladem (vynuceným prací studenta na artefaktu ke zmíněnému PLDI článku), finální obsah byl dostatečně konzultován.

Student dostal zadánu studijní literaturu, další vhodnou literaturu si dokázal najít sám.

Evaluation level: is within the usual extent

The main body of the thesis consists of 46 pages of technical writing of exceptionally high quality.

Both the typographical and linguistic aspects of the thesis are at the level of a high-quality scientific publication.

The practical output of the thesis consists of two parts: improvements to the construction of deterministic RSAs from regular expressions and a matcher based on deterministic RSAs.

In the first part, the author builds upon (his) previous work by proposing several heuristics for constructing nondeterministic RAs from regular expressions and subsequently determinizing them into RSAs. These optimizations significantly improve the practicality of the RSA-based approach to regular-expression matching by enabling the construction of smaller automata in less time.

The second part presents a cleverly designed RSA matcher in the form of an optimized virtual machine (VM). Although the design is inspired by existing technologies for NFA simulation, adapting these ideas to RSAs required several elegant solutions to problems related to instruction-set design, program layout, code generation, and other implementation aspects. Large alphabets (Unicode) are handled using prefix trees that classify UTF-8 encodings of symbols into minterm character sets associated with a given state. Furthermore, MTBDDs are used to minimize the number of register tests. Both features highlight the tremendous amount of engineering effort invested in the implementation.

The thesis also presents a detailed experimental evaluation of the implementation, demonstrating that the proposed approach outperforms state-of-the-art matchers on regular expressions with backreferences that can be used in so-called ReDoS attacks.

The implementation is also part of a publication co-authored by the student that has been accepted to PLDI 2026 (CORE A*). Consequently, part of the experimental evaluation presented in the thesis has been independently reproduced by multiple reviewers, and the artifact received the highest possible rating (Available, Functional, Reusable).

Evaluation level: very difficult assignment

The assignment is very challenging. Numerous models for recognizing different classes of data languages have been introduced in the literature. The assignment requires determining a suitable model for representing regular expressions with backreferences; thus, the student must familiarize themselves with the available models at a deeper level in order to assess their suitability for this task.

Based on an agreement with the supervisor, the student is required to work on one of the following two tasks. First, the student may advance our theoretical understanding of a particular model by proving various properties, such as investigating the decidability and complexity of different decision problems associated with the model. Such a task is extremely demanding, as discovering a proof often requires a combination of mathematical experience, creativity, and luck, with no guarantee of success. Alternatively, the student may focus on developing efficient algorithms for various problems related to the model. Finding sound and complete algorithms is itself a difficult task that becomes easier only with experience. Moreover, designing efficient algorithms requires an in-depth understanding of the subtleties of a particular model as well as strong engineering foresight.