Original title:
Lineární verze Holubova algoritmu
Translated title:
Linear version of Holub's algorithm
Authors:
Tvrdý, David ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee) Document type: Bachelor's theses
Year:
2020
Language:
cze Abstract:
[cze][eng] Tato práce studuje lineární algoritmus, který pro zadané slovo rozhodne, zda existuje netriviální homomorfismus, jehož je dané slovo pevným bodem. Dále jsou v práci popsány pomocné datové struktury, které jsou pro lineární časovou složitost důležité. Součástí práce je i vlastní implementace tohoto algoritmu v jazyce Java včetně vizualizace chodu algoritmu pro konkrétní vstupy. 1This work studies a linear agorithm which decides if a given word is a fixed point of any nontrivial morphism. This work also contains a description of auxiliary data structures which are crucial for linear time complexity of the algorithm. A Java implementation of the algorithm is provided along with a step-by-step visualization for particular input words. 1
Keywords:
fixed point; linear algorithm; morphic factorization; lineární algoritmus; morfický rozklad; pevný bod
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/118911