Lineární verze Holubova algoritmu
| Thesis title in Czech: | Lineární verze Holubova algoritmu |
|---|---|
| Thesis title in English: | Linear version of Holub's algorithm |
| Key words: | morfický rozklad, pevný bod, lineární algoritmus |
| English key words: | morphic factorization, fixed point, linear algorithm |
| Academic year of topic announcement: | 2019/2020 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Štěpán Holub, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 07.11.2019 |
| Date of assignment: | 07.11.2019 |
| Confirmed by Study dept. on: | 21.11.2019 |
| Date and time of defence: | 29.06.2020 10:00 |
| Date of electronic submission: | 04.06.2020 |
| Date of submission of printed version: | 04.06.2020 |
| Date of proceeded defence: | 29.06.2020 |
| Opponents: | doc. Mgr. et Mgr. Jan Žemlička, Ph.D. |
| Guidelines |
| Student se seznámí s lineární verzí algoritmu pro testování homomorfní primitivity slov. Popíše jeho fungování a implementuje ho. |
| References |
| Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Linear-time version of Holub's algorithm for morphic imprimitivity testing, Theoretical Computer Science 602, 7-21 (2015).
Štěpán Holub, Polynomial algorithm for fixed points of nontrivial morphisms, Discrete Mathematics 309, 5069-5076 (2009). Vojtěch Matocha, Algoritmus pro pevné body homomorfismů na slovech, bakalářská práce, MFF UK, 2011. |