Let be a substitution over a 2-letter alphabet, say . If and begin with and respectively, has two fixed points beginning with and respectively.We characterize substitutions with two cofinal fixed points (i.e., which differ only by prefixes). The proof is a combinatorial one, based on the study of repetitions of words in the fixed points.
Nous donnons une représentation géométrique des suites doubles uniformément récurrentes de fonction de complexité rectangulaire . Nous montrons que ces suites codent l’action d’une -action définie par deux rotations irrationnelles sur le cercle unité. La preuve repose sur une étude des suites doubles dont les lignes sont des suite sturmiennes de même langage.
On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de -automates déterministes dénombrables de degré borné, ou de manière équivalente, engendrés par des substitutions de longueur constante uniformément bornées sur un alphabet dénombrable. En particulier, on montre que la complexité de tels mots est au plus polynomiale et que, sur plusieurs exemples, elle est au plus de l’ordre de grandeur de .
We consider subshifts arising from primitive substitutions, which are known to be uniquely ergodic dynamical systems. In order to precise this point, we introduce a symbolic notion of discrepancy. We show how the distribution of such a subshift is in part ruled by the spectrum of the incidence matrices associated with the underlying substitution. We also give some applications of these results in connection with the spectral study of substitutive dynamical systems.
The box parameter for words counts how often two letters w j and w k define a “box” such that all the letters w j+1; ..., w k−1 fall into that box. It is related to the visibility parameter and other parameters on words. Three models are considered: Words over a finite alphabet, permutations, and words with letters following a geometric distribution. A typical result is: The average box parameter for words over an M letter alphabet is asymptotically given by 2n − 2n H M/M, for fixed M and n → ∞.
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.
Generalizing the results of Thue (for n = 2) [Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67] and of Klepinin and Sukhanov (for n = 3) [Discrete Appl. Math. 114 (2001) 155–169], we prove that for all n ≥ 2, the critical exponent of the Arshon word of order n is given by (3n–2)/(2n–2), and this exponent is attained at position 1.
It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another...