Catálogo de publicaciones - libros

In a preceding article, we have studied the family of words derivated from characteristic Sturmian words. This study has lead to a new proof of the characterization of characteristic Sturmian words which are fixed points of morphisms. In this article, we extend this approach to all Sturmian words. The Sturmian words viewed as dynamical systems play an important role in obtaining this generalization.

In the case of finite words, a Schützenberger theorem proves that the star-free sets are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets. The variety theorem of Eilenberg offers a general framework for the algebraic characterization of recognizable sets: it establishes a one-to-one correspondence between varieties of languages of finite words and pseudo-varieties of algebras. This paper contains extensions of those two well-known results to words on countable scattered linear orderings.

In this paper we consider decidability questions that are related to the membership problem in matrix semigroups. In particular we consider the membership of a particular invertible diagonal matrix in a matrix semigroup and then a scalar matrix, which has a separate geometric interpretation. Both problems have been open for any dimensions and are shown to be undecidable in dimenesion 4 with integral matrices and in dimension 3 with rational matrices by a reduction of the Post Correspondence Problem (PCP). Although the idea of PCP reduction is standard for such problems, we suggest a new coding technique to cover the case of diagonal matrices.

In a preceding paper, Bruyère and the second author introduced automata, as well as rational expressions, which allow to deal with words indexed by linear orderings. A Kleene-like theorem was proved for words indexed by countable scattered linear orderings. In this paper we extend this result to languages of words indexed by all linear orderings.

We introduce and investigate revolving-input finite automata, which are nondeterministic finite automata with the additional ability to shift the remaining part of the input. We consider three different modes of shifting, namely revolving to the left, revolving to the right, and circular interchanging. We show that the latter operation does not increase the computational power of finite automata, even if the number of revolving operations is unbounded. The same result is obtained for the former two operations in case of an arbitrary but constant number of applications allowed. An unbounded number of these operations leads to language families that are properly contained in the family of context-sensitive languages, are incomparable with the family of context-free languages, and are strictly more powerful than regular languages. Moreover, we show that right revolving can be simulated by left revolving, when considering the mirror image of the input.

For heuristic reasons billiard words may have more palindromic factors than any other words. Many results are already known, concerning the palindromic factors and the palindromic prefixes of Sturmian words and billiard words on two letters. We give general results concerning multidimensional billiard words, which describe very different situations. In some cases, these words have arbitrary long palindromic prefix factors. In other cases, at the opposite, they have finitely many distinct palindromic factors. AMS classification: 68R15.

We consider paths in the square lattice and use a valuation called the winding number in order to exhibit some combinatorial properties on these paths. As a corollary, we obtain a characteristic property of self-avoiding closed paths, generalizing in this way a recent result of Daurat and Nivat (2003) on the boundary properties of polyominoes concerning salient and reentrant points.

We study some structural and combinatorial properties of Sturmian palindromes, i.e., palindromic finite factors of Sturmian words. In particular, we give a formula which permits to compute in an exact way the number of Sturmian palindromes of any length. Moreover, an interesting characterization of Sturmian palindromes is obtained.

In this paper are considered one-dimensional tilings arising from some Pisot numbers encountered in quasicrystallography as the quadratic Pisot units and the cubic Pisot unit associated with 7-fold symmetry, and also the Tribonacci number. We give characterizations of the Voronoi cells of such tilings, using word combinatorics and substitutions.

In this paper we describe a factorial language, denoted by L ( S , k , r ), that contains all words that occur in a string S up to k mismatches every r symbols. Then we give some combinatorial properties of a parameter, called repetition index and denoted by R ( S , k , r ), defined as the smallest integer h ≥ 1 such that all strings of this length occur at most in a unique position of the text S up to k mismatches every r symbols. We prove that R ( S , k , r ) is a non-increasing function of r and a non-decreasing function of k and that the equation r = R ( S , k , r ) admits a unique solution. The repetition index plays an important role in the construction of an indexing data structure based on a trie that represents the set of all factors of L ( S , k , r ) having length equal to R ( S , k , r ). For each word x ∈ L ( S , k , r ) this data structure allows us to find the list occ ( x ) of all occurrences of the word x in a text S up to k mismatches every r symbols in time proportional to | x |+| occ ( x )|.