Restartovací automaty s h-lexikalizací

• Thesis title in Czech: Restartovací automaty s h-lexikalizací
• Thesis title in English: On h-lexicalized Automata
• Key words: restartovací automat|h-lexikalizovaný automat|vlastnost zachování správnosti|vlastnost zachování chyby|lexikální disambiguace|redukční analýza
• English key words: lexicalized syntactic analysis|restarting automaton|correctness preserving computation|error preserving computation|analysis by reduction
• Academic year of topic announcement: 2024/2025
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: Mgr. Marta Vomlelová, Ph.D.
• Author: Bc. Václav Kouřil - assigned and confirmed by the Study Dept.
• Date of registration: 30.05.2024
• Date of assignment: 25.06.2024
• Confirmed by Study dept. on: 27.06.2024
• Date and time of defence: 20.06.2025 09:00
• Date of electronic submission: 07.05.2025
• Date of submission of printed version: 07.05.2025
• Date of proceeded defence: 20.06.2025
• Opponents: RNDr. František Mráz, CSc.
• Advisors: Martin Plátek, CSc.

Guidelines

Student popíše restartovací automaty, škálu jejich povolených operací a morfizmus z pracovní abecedy do abecedy vstupní. Zavede operaci silný restart a ukáže jí na příkladech. Zvolí konkrétní část hierarchie složitosti - např. z [1], jazyky rozlišující jednotlivé třídy složitosti popíše pomocí restartovacích automatů.
Student implementuje simulátor restartovacích automatů, na kterém ověří, že jím navržené automaty přijímají dané jazyky.

References

[1] Plátek, Martin and Friedrich Otto: On h-Lexicalized Restarting Automata, International Conference on Automata and Formal Languages (2017).
[2] Martin Plátek, Friedrich Otto, and František Mráz: One-Way Restarting Automata and Their Sensitivitys, International Journal of Foundations of Computer Science 2022 33:03n04, 371-387