Two Equivalence Relations on Digital Lines with Irrational Slopes. A Continued Fraction Approach to Upper Mechanical Words
2009 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 410, no 38--40, 3655-3669 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
Elsevier , 2009. Vol. 410, no 38--40, 3655-3669 p.
digital line, upper mechanical word, characteristic word, irrational slope, continued fraction, hierarchy, run, classes of digital lines, classes of words, Fibonacci numbers
IdentifiersURN: urn:nbn:se:uu:diva-105925DOI: 10.1016/j.tcs.2009.04.026ISI: 000269683400008OAI: oai:DiVA.org:uu-105925DiVA: diva2:222873