Displaying 21 – 40 of 137

Showing per page

Automaticity IV : sequences, sets, and diversity

Jeffrey Shallit (1996)

Journal de théorie des nombres de Bordeaux

This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of N (the natural numbers). If ( s ( i ) ) i 0 is a sequence over a finite alphabet Δ , then we define the k -automaticity of s , A s k ( n ) , to be the smallest possible number of states in any deterministic finite automaton that, for all i with 0 i n , takes i expressed in base k as input and computes s ( i ) . We give examples of sequences that have high automaticity in all bases k ; for example, we show that the characteristic...

Best simultaneous diophantine approximations of some cubic algebraic numbers

Nicolas Chevallier (2002)

Journal de théorie des nombres de Bordeaux

Let α be a real algebraic number of degree 3 over whose conjugates are not real. There exists an unit ζ of the ring of integer of K = ( α ) for which it is possible to describe the set of all best approximation vectors of θ = ( ζ , ζ 2 ) .’

Boundedness of oriented walks generated by substitutions

F. M. Dekking, Z.-Y. Wen (1996)

Journal de théorie des nombres de Bordeaux

Let x = x 0 x 1 be a fixed point of a substitution on the alphabet a , b , and let U a = - 1 - 1 0 1 and U b = 1 1 0 1 . We give a complete classification of the substitutions σ : a , b according to whether the sequence of matrices U x 0 U x 1 U x n n = 0 is bounded or unbounded. This corresponds to the boundedness or unboundedness of the oriented walks generated by the substitutions.

Cobham's theorem for substitutions

Fabien Durand (2011)

Journal of the European Mathematical Society

The seminal theorem of Cobham has given rise during the last 40 years to a lot of work about non-standard numeration systems and has been extended to many contexts. In this paper, as a result of fifteen years of improvements, we obtain a complete and general version for the so-called substitutive sequences. Let α and β be two multiplicatively independent Perron numbers. Then a sequence x A , where A is a finite alphabet, is both α -substitutive and β -substitutive if and only if x is ultimately periodic....

Codages de rotations et phénomènes d'autosimilarité

Boris Adamczewski (2002)

Journal de théorie des nombres de Bordeaux

Nous étudions une classe de suites symboliques, les codages de rotations, intervenant dans des problèmes de répartition des suites ( n α ) n et représentant une généralisation géométrique des suites sturmiennes. Nous montrons que ces suites peuvent être obtenues par itération de quatre substitutions définies sur un alphabet à trois lettres, puis en appliquant un morphisme de projection. L’ordre d’itération de ces applications est gouverné par un développement bi-dimensionnel de type “fraction continue”...

Combinatoire de mots récurrents de complexité n+2

Idrissa Kaboré, Théodore Tapsoba (2007)

RAIRO - Theoretical Informatics and Applications

Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul n, exactement n+2 facteurs de longueur n. Nous définissons également la notion d'insertion k à k sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l'équilibre et la palindromie d'une classe particulière de mots de complexité n+2 que nous appelons mots quasi-sturmiens...

Combinatorial and arithmetical properties of infinite words associated with non-simple quadratic Parry numbers

Lubomíra Balková, Edita Pelantová, Ondřej Turek (2007)

RAIRO - Theoretical Informatics and Applications

We study some arithmetical and combinatorial properties of β-integers for β being the larger root of the equation x2 = mx - n,m,n ∈ ℵ, m ≥ n +2 ≥ 3. We determine with the accuracy of ± 1 the maximal number of β-fractional positions, which may arise as a result of addition of two β-integers. For the infinite word uβ> coding distances between the consecutive β-integers, we determine precisely also the balance. The word uβ> is the only fixed point of the morphism A → Am-1B and B → Am-n-1B. In...

Complexité des suites de Rudin-Shapiro généralisées

J.-P. Allouche, J. O. Shallit (1993)

Journal de théorie des nombres de Bordeaux

La complexité d’une suite infinie est définie comme la fonction qui compte le nombre de facteurs de longueur k dans cette suite. Nous prouvons ici que la complexité des suites de Rudin-Shapiro généralisées (qui comptent les occurrences de certains facteurs dans les développements binaires d’entiers) est ultimement affine.

Complexité et automates cellulaires linéaires

Valérie Berthé (2010)

RAIRO - Theoretical Informatics and Applications

The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in / l , and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

Complexity of Hartman sequences

Christian Steineder, Reinhard Winkler (2005)

Journal de Théorie des Nombres de Bordeaux

Let T : x x + g be an ergodic translation on the compact group C and M C a continuity set, i.e. a subset with topological boundary of Haar measure 0. An infinite binary sequence a : { 0 , 1 } defined by a ( k ) = 1 if T k ( 0 C ) M and a ( k ) = 0 otherwise, is called a Hartman sequence. This paper studies the growth rate of P a ( n ) , where P a ( n ) denotes the number of binary words of length n occurring in a . The growth rate is always subexponential and this result is optimal. If T is an ergodic translation x x + α ...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We study the complexity of the infinite word u β associated with the Rényi expansion of 1 in an irrational base β > 1 . When β is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity ( n ) = n + 1 . For β such that d β ( 1 ) = t 1 t 2 t m is finite we provide a simple description of the structure of special factors of the word u β . When t m = 1 we show that ( n ) = ( m - 1 ) n + 1 . In the cases when t 1 = t 2 = = t m - 1 or t 1 > max { t 2 , , t m - 1 } we show that the first difference of the complexity function ( n + 1 ) - ( n ) takes value in { m - 1 , m } for every n , and consequently we determine...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

We study the complexity of the infinite word uβ associated with the Rényi expansion of 1 in an irrational base β > 1. When β is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity C(n) = n + 1. For β such that dβ(1) = t1t2...tm is finite we provide a simple description of the structure of special factors of the word uβ. When tm=1 we show that C(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1or t1 > max{t2,...,tm-1} we show that the first difference of...

Currently displaying 21 – 40 of 137