All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3 Next

Displaying 41 – 60 of 79

Showing per page

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...

Complexity of testing morphic primitivity

Štěpán Holub, Vojtěch Matocha (2013)

Kybernetika

We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in 𝒪 ( m · n ) , where n is the length of the word and m the size of the alphabet.

Connectedness of fractals associated with Arnoux–Rauzy substitutions

Valérie Berthé, Timo Jolivet, Anne Siegel (2014)

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

Rauzy fractals are compact sets with fractal boundary that can be associated with any unimodular Pisot irreducible substitution. These fractals can be defined as the Hausdorff limit of a sequence of compact sets, where each set is a renormalized projection of a finite union of faces of unit cubes. We exploit this combinatorial definition to prove the connectedness of the Rauzy fractal associated with any finite product of three-letter Arnoux–Rauzy substitutions.

Construction du treillis de Galois d'une relation binaire

A. Guénoche (1990)

Mathématiques et Sciences Humaines

Cet article constitue une présentation unifiée des principales méthodes de construction du treillis de Galois d'une correspondance. Nous rappelons d'abord sa définition, puis nous décrivons quatre algorithmes de construction des éléments du treillis qui sont les rectangles maximaux de la relation binaire. Ces algorithmes ne sont pas originaux. Les descriptions précises de algorithmes, le plus souvent absentes des publications originales, permettent une programmation simple, dans un langage procédural...

Construction of a Deterministic ω-Automaton Using Derivatives

Roman R. Redziejowski (2010)

RAIRO - Theoretical Informatics and Applications

A deterministic automaton recognizing a given ω-regular language is constructed from an ω-regular expression with the help of derivatives. The construction is related to Safra's algorithm, in about the same way as the classical derivative method is related to the subset construction.

Continued fractions and transcendental numbers

Boris Adamczewski, Yann Bugeaud, Les Davison (2006)

Annales de l’institut Fourier

The main purpose of this work is to present new families of transcendental continued fractions with bounded partial quotients. Our results are derived thanks to combinatorial transcendence criteria recently obtained by the first two authors in [3].

Currently displaying 41 – 60 of 79