Stacks, queues and tracks: layouts of graph subdivisions.
Standard factors of Sturmian words
Among the various ways to construct a characteristic Sturmian word, one of the most used consists in defining an infinite sequence of prefixes that are standard. Nevertheless in any characteristic word c, some standard words occur that are not prefixes of c. We characterize all standard words occurring in any characteristic word (and so in any Sturmian word) using firstly morphisms, then standard prefixes and finally palindromes.
Stapled sequences and stapling coverings of natural numbers.
Straight-line drawings of binary trees with linear area and arbitrary aspect ratio.
Straight-line drawings on restricted integer grids in two and three dimensions.
Strict refinement for direct sums and graphs.
Strings with maximally many distinct subsequences and substrings.
Strongly automatic semigroups
Dans cet article, nous introduisons la notion de semi-groupe fortement automatique, qui entraîne la notion d’automaticité des semi-groupes usuelle. On s’intéresse particulièrement aux semi-groupes de développements en base , pour lesquels on obtient un critère de forte automaticité.
Strongly compatible total orders on free monoids.
Structural Properties of Recursively Partitionable Graphs with Connectivity 2
A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition of G must...
Study of irreducible balanced pairs for substitutive languages
Let be a language. A balanced pair (u,v) consists of two words u and v in which have the same number of occurrences of each letter. It is irreducible if the pairs of strict prefixes of u and v of the same length do not form balanced pairs. In this article, we are interested in computing the set of irreducible balanced pairs on several cases of languages. We make connections with the balanced pairs algorithm and discrete geometrical constructions related to substitutive languages. We characterize...
Studying graph - stability to apprehend relative hardness of constructive-non-constructive approximation
Sturm numbers and substitution invariance of 3iet words.
Sturmian jungle (or garden?) on multiliteral alphabets
The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions...
Sturmian jungle (or garden?) on multiliteral alphabets
The properties characterizing Sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of Sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of Sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions...
Sturmian morphisms. (Morphismes de Sturm.)
Substitution invariant sturmian bisequences
We prove that a Sturmian bisequence, with slope and intercept , is fixed by some non-trivial substitution if and only if is a Sturm number and belongs to . We also detail a complementary system of integers connected with Beatty bisequences.
Substitutions, abstract number systems and the space filling property
In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.
Substitutions par des motifs en dimension 1
Une substitution est un morphisme de monoïdes libres : chaque lettre a pour image un mot, et l'image d'un mot est la concaténation des images de ses lettres. Cet article introduit une généralisation de la notion de substitution, où l'image d'une lettre n'est plus un mot mais un motif, c'est-à-dire un “mot à trous”, l'image d'un mot étant obtenue en raccordant les motifs correspondant à chacune de ses lettres à l'aide de règles locales. On caractérise complètement les substitutions par des motifs...
Substitutions with Cofinal Fixed Points
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.