On appelle échange d’intervalles l’application qui consiste à réordonner les intervalles d’une partition de suivant une permutation donnée. Dans le cas des partitions en trois intervalles, nous donnons une caractérisation combinatoire des suites codant, d’après la partition définissant l’échange, l’orbite d’un point de sous l’action de cette transformation.
We present an on-line linear time and space algorithm to check if an integer array is the border array of at least one string built on a bounded or unbounded size alphabet . First of all, we show a bijection between the border array of a string and the skeleton of the DFA recognizing , called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a skeleton of SMA...
We present an on-line linear time and space algorithm to check if an integer array f is the border array of at least one string w built on a bounded or unbounded size alphabet Σ. First of all, we show a bijection between the border array of a string w and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a...
We inductively describe an embedding of a complete ternary tree Tₕ of height h into a hypercube Q of dimension at most ⎡(1.6)h⎤+1 with load 1, dilation 2, node congestion 2 and edge congestion 2. This is an improvement over the known embedding of Tₕ into Q. And it is very close to a conjectured embedding of Havel [3] which states that there exists an embedding of Tₕ into its optimal hypercube with load 1 and dilation 2. The optimal hypercube has dimension ⎡(log₂3)h⎤ ( = ⎡(1.585)h⎤) or ⎡(log₂3)h⎤+1....
It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.
We associate with a word on a finite alphabet an episturmian (or Arnoux-Rauzy) morphism and a palindrome. We study their relations with the similar ones for the reversal of . Then when we deduce, using the sturmian words that are the fixed points of the two morphisms, a proof of a Galois theorem on purely periodic continued fractions whose periods are the reversal of each other.
We associate with a word w on a finite alphabet A an episturmian (or Arnoux-Rauzy) morphism and a palindrome. We study their relations with the similar ones for the reversal of w. Then when |A|=2 we deduce, using the Sturmian words that are the fixed points of the two morphisms, a proof of a Galois theorem on purely periodic continued fractions whose periods are the reversal of each other.
In this paper, we survey the rich theory of infinite episturmian words which generalize to any finite alphabet, in a rather resembling way, the well-known family of Sturmian words on two letters. After recalling definitions and basic properties, we consider episturmian morphisms that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties...
It is well-known that some of the most basic properties of words, like the commutativity () and the conjugacy (), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation has only periodic solutions in a free monoid, that is, if holds with integers , then there exists a word such that are powers of . This result, which received a lot of attention, was first proved by Lyndon and...