Christoffelove riječi

master's thesis

• Title (english): Christoffel's words
• Author: Judita Motočić
• Mentor: Tomislav Pejković (mentor)
• Committee member: Tomislav Pejković (predsjednik povjerenstva)
• Committee member: Matija Bašić (član povjerenstva)
• Committee member: Ozren Perše (član povjerenstva)
• Committee member: Maja Resman (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-12-02, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Neka su p i q nenegativni relativno prosti brojevi i neka je dužina \(\overline{AB}\) takva da točka A ima cjelobrojne koordinate te \(B=A+(p,q) \). Christoffelova riječ nagiba \(\frac{q}{p}\) je riječ u slobodnom monoidu \(\{a,b\}^*\) koja kodira Christoffelov put istog nagiba, odnosno put u rešetki od točke A do točke B takav da poligon omeđen dužinom \(\overline{AB}\) i tim putem u nutrini ne sadrži cjelobrojne točke. Reznu riječ dobivamo tako da promatramo sjecišta otvorene dužine AB s pravcima cjelobrojne rešetke. Christoffelove riječi moguće je rekurzivno konstruirati. Svaka prava Christoffelova riječ može se na jedinstven način prikazati kao produkt dviju Christoffelovih riječi. U ovom radu proučavamo neka svojstva Christoffelovih riječi, njihovu vezu s reznim riječima te faktorizacijom tih riječi. Također definiramo odgovarajuća binarna stabla koja sadrže Christoffelove riječi ili njihove parove. Na kraju su izloženi osnovni algoritmi za konstrukciju i prepoznavanje Christoffelovih riječi.

Abstract (english)

Let p and q be non-negative, relatively prime integers and \(\overline{AB}\) a segment with integral point A and \(B=A+(p,q) \). The Christoffel's word of slope \(\frac{q}{p}\) is the word in the free monoid \(\{a,b\}^*\) coding the Christoffel9s path of the same slope, that is, the lattice path from point A to point B such that the polygon delimited by segment \(\overline{AB}\) and the path has no interior integer points. The cutting word is obtained by considering intersections of the open segment AB with the coordinate lines. Christoffel's words can be constructed recursively. Each proper Christoffel's word is uniquely the product of two Christoffel's words. We study some properties of Christoffel's words, their connection with cutting words as well as the factorization of those words. We also define binary trees containing Christoffel'swords and pairs of such words. At the end we give basic algorithms for construction and identification of Christoffel'sl words.

• Keywords: Christoffelov put; rezna riječ; binarna stabla
• Keywords (english): Christoffel's way; cutting word; binary trees
• Language: croatian
• URN:NBN: urn:nbn:hr:217:358393
• Study programme: Title: Mathematics Education; specializations in: Mathematics Education; Course: Mathematics Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike (magistar/magistra edukacije matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-12-15 11:52:53