Algoritmus pro pevné body homomorfismů na slovech

• Thesis title in Czech: Algoritmus pro pevné body homomorfismů na slovech
• Thesis title in English: Algorithm for word morphisms fixed points
• Key words: pevný bod, polynomiální algoritmus, union-find, složitost
• English key words: fixed point, polynomial algorithm, union-find, complexity
• Academic year of topic announcement: 2010/2011
• 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: 12.11.2010
• Date of assignment: 12.11.2010
• Date and time of defence: 23.06.2011 00:00
• Date of electronic submission: 24.05.2011
• Date of submission of printed version: 26.05.2011
• Date of proceeded defence: 23.06.2011
• Opponents: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Guidelines

Student se seznámí s algoritmem určujícím, zda dané slovo je netriviálním pevným bodem nějakého homomorfismu. Analyzuje složitost algoritmu a naprogramuje co nejrychlejší implementaci.

References

Tom Head,Fixed languages and the adult languages of OL schemes, Internat. J. Comput. Math. 10 (1981/82), no. 2, 103-107.
Štěpán Holub, Polynomial algorithm for fixed points of nontrivial morphisms, Discrete Mathematics 309 5069-5076 (2009).

Preliminary scope of work

Jedná se o algoritmus založený na jednoduchých kombinatorických úvahách. Jeho složitost je v naivní implementaci kvadratická, s trochou úvah n.log n, ale mělo by to jít ještě trochu rychleji. Základem snižování složitosti budou úvahy nad algoritmickým principem "union and find".