Algorithms for word equations
| Thesis title in Czech: | |
|---|---|
| Thesis title in English: | Algorithms for word equations |
| Key words: | rovnice na slovech, algoritmus |
| English key words: | word equations, algorithms |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | dissertation |
| Thesis language: | anglič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: | 26.09.2012 |
| Date of assignment: | 26.09.2012 |
| Confirmed by Study dept. on: | 05.12.2012 |
| Guidelines |
| Student nastuduje existující algoritmy pro řešení rovnic na slovech, zejména obecné algoritmy Makanina a Pladowského. Zejména Plandowského algoritmy co nejsrozumitelněji popíše a pokusí se je zjednodušit. Jedním z cílů tohoto úsilí je získat netriviální poznatky o jejich složitosti.
|
| References |
| Lothaire, M., Combinatorics on Words, Addison-Wesley, 1983
Lothaire, M., Algebraic Combinatorics on Words, Cambridge University Press, 2002 Plandowski, W., An efficient algorithm for solving word equations. STOC 2006: 467-476 |