Complexity of infinite sequences with zero entropy
Complexity of infinite words associated with beta-expansions
We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When we show that . In the cases when or we show that the first difference of the complexity function takes value in for every , and consequently we determine...
Complexity of infinite words associated with beta-expansions
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
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 , where is the length of the word and the size of the alphabet.
Computational aspects of lucidity-driven graph clustering.
Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems.
Computing and drawing isomorphic subgraphs.
Computing communities in large networks using random walks.
Computing radial drawings on the minimum number of circles.
Confluent drawings: visualizing non-planar diagrams in a planar way.
Congestion optimale du plongement de l’hypercube dans la chaîne
Connectedness of fractals associated with Arnoux–Rauzy substitutions
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.
Connections between binary patterns and paperfolding
Connectivity of planar graphs.
Construction du treillis de Galois d'une relation binaire
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, évaluation et amélioration systématiques de structures de données
Construction of a deterministic -automaton using derivatives
Construction of a Deterministic ω-Automaton Using Derivatives
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
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].
Continued fractions, Fibonacci numbers, and some classes of irrational numbers.