| 1. |
- Uscka-Wehlou, Hanna, 1973-
(författare)
-
A Run-hierarchical Description of Upper Mechanical Words with Irrational Slopes Using Continued Fractions
- 2008
-
Ingår i: Proceedings of the 12th Mons Theoretical Science Days, Mons, Belgium 27-30 August 2008. - Mons, Belgium : Mons University.
-
Konferensbidrag (refereegranskat)abstract
- The main result is a run-hierarchical description (by continued fractions) of upper mechanical words with positive irrational slope less than 1 and intercept 0. We compare this description with two classical methods of forming of such words. In order to be able to perform the comparison, we present a quantitative analysis of our method. We use the denominator of the convergents of the continued fraction expansion of the slope to compute the length of the prefixes obtained by our method. Due to the special treatment which is given to the elements equal to 1, our method gives in some cases longer prefixes than the two other methods. Our method reflects the hierarchy of runs, by analogy to digital lines, which can give a new understanding of the construction of upper mechanical words.
|
|
| 2. |
- Uscka-Wehlou, Hanna, 1973-
(författare)
-
Continued fractions and digital lines with irrational slopes
- 2008
-
Ingår i: Proceedings of DGCI, the 14th International Conference on DISCRETE GEOMETRY for COMPUTER IMAGERY. DGCI 2008. - Berlin Heidelberg : Springer-Verlag. - 9783540791256 ; , s. 93-104
-
Konferensbidrag (refereegranskat)abstract
- This paper expands on previous work on relationships between digital linesand continued fractions (CF). The main result is a parsimonious description of the construction of the digital line based only on the elements of the CF representing its slope and containing only simple integer computations. The description reflects the hierarchy of digitization runs, which raises the possibility of dividing digital lines into equivalence classes depending on the CF expansions of their slopes. Our work is confined to irrational slopes since, to our knowledge, there exists no such description for these, in contrast to rational slopes which have been extensively examined. The description is exact and does not use approximations by rationals. Examples of lines withirrational slopes and with very simple digitization patterns are presented. These include both slopes with periodic and non-periodic CF expansions, i.e.\ both quadratic surds and other irrationals.
|
|
| 3. |
- Uscka-Wehlou, Hanna, 1973-
(författare)
-
Digital lines, Sturmian words, and continued fractions
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis we present and solve selected problems arising from digital geometry and combinatorics on words. We consider digital straight lines and, equivalently, upper mechanical words with positive irrational slopes a<1 and intercept 0. We formulate a continued fraction (CF) based description of their run-hierarchical structure. Paper I gives a theoretical basis for the CF-description of digital lines. We define for each irrational positive slope less than 1 a sequence of digitization parameters which fully specifies the run-hierarchical construction. In Paper II we use the digitization parameters in order to get a description of runs using only integers. We show that the CF-elements of the slopes contain the complete information about the run-hierarchical structure of the line. The index jump function introduced by the author indicates for each positive integer k the index of the CF-element which determines the shape of the digitization runs on level k. In Paper III we present the results for upper mechanical words and compare our CF-based formula with two well-known methods, one of which was formulated by Johann III Bernoulli and proven by Markov, while the second one is known as the standard sequences method. Due to the special treatment of some CF-elements equal to 1 (essential 1's in Paper IV), our method is currently the only one which reflects the run-hierarchical structure of upper mechanical words by analogy to digital lines. In Paper IV we define two equivalence relations on the set of all digital lines with positive irrational slopes a<1. One of them groups into classes all the lines with the same run length on all digitization levels, the second one groups the lines according to the run construction in terms of long and short runs on all levels. We analyse the equivalence classes with respect to minimal and maximal elements. In Paper V we take another look at the equivalence relation defined by run construction, this time independently of the context, which makes the results more general. In Paper VI we define a run-construction encoding operator, by analogy with the well-known run-length encoding operator. We formulate and present a proof of a fixed-point theorem for Sturmian words. We show that in each equivalence class under the relation based on run length on all digitization levels (as defined in Paper IV), there exists exactly one fixed point of the run-construction encoding operator.
|
|
| 4. |
- Uscka-Wehlou, Hanna, 1973-
(författare)
-
Run-hierarchical structure of digital lines with irrational slopes in terms of continued fractions and the Gauss map
- 2009
-
Ingår i: Pattern Recognition. - : Elsevier. - 0031-3203 .- 1873-5142. ; 42:10, s. 2247-2254
-
Tidskriftsartikel (refereegranskat)abstract
- We study relations between digital lines and continued fractions. The main result is a parsimonious description of the construction of the digital line based only on the elements of the continued fraction representing its slope and containing only simple integer computations. The description reflects the hierarchy of digitization runs, which raises the possibility of dividing digital lines into equivalence classes depending on the continued fraction expansions of their slopes. Our work is confined to irrational slopes since, to our knowledge,there exists no such description for these, in contrast to rational slopes which have been extensively examined. The description is exact (it does not use approximations by rationals). Examples of lines with irrational slopes and with very simple digitization patterns are presented. These include both slopes with periodic and non-periodic continued fraction expansions, i.e.\ both quadratic surds and other irrationals. We also derive the connection between the Gauss map and the digitization parameters introduced by the author in 2007.
|
|
| 5. |
- Uscka-Wehlou, Hanna, 1973-
(författare)
-
Sturmian words with balanced construction
- 2009
-
Ingår i: Proceedings of Words 2009, the 7th International Conference on Words (Salerno, Italy), 14--18 September 2009. - Italy : Salerno University.
-
Konferensbidrag (refereegranskat)abstract
- In this paper we define Sturmian words with balanced construction. We formulate a fixed-point theorem for Sturmian words and analyze the set of all fixed points. The inspiration for this work came from the Kolakoski word and the general idea of self-reading sequences by P\u{a}un and Salomaa. The basis for this article is the author's earlier research on the influence of the continued fraction elements in the expansion of a positive irrational slope $a<1$ on the construction of runs for the upper mechanical word with slope $a$and intercept $0$.
|
|
| 6. |
- Uscka-Wehlou, Hanna, 1973-
(författare)
-
Two Equivalence Relations on Digital Lines with Irrational Slopes. A Continued Fraction Approach to Upper Mechanical Words
- 2009
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 410:38--40, s. 3655-3669
-
Tidskriftsartikel (refereegranskat)abstract
- We examine the influence of the elements of the continued fraction (CF) expansion of irrational positive a less than 1 on the construction of runs in the digitization of the positive half line y=ax or, equivalently, on the run-hierarchical structure of the upper mechanical word with slope a and intercept 0. Special attention is given to the CF elements equal to 1.We define two complementary equivalence relations on the set of slopes, based on their CF expansions. A new description of digital lines is presented; we show how to define a straight line or upper mechanical word by two sequences of positive integers fulfilling some extra conditions. These equivalence relations and this new description enable us to analyze the construction of digital lines and upper mechanical words. The analysis of suprema of equivalence classes under one of these relations leads to a result which involves Fibonacci numbers.
|
|
