Displaying similar documents to “Languages under substitutions and balanced words”

On low-complexity bi-infinite words and their factors

Alex Heinis (2001)

Journal de théorie des nombres de Bordeaux

Similarity:

In this paper we study bi-infinite words on two letters. We say that such a word has stiffness k if the number of different subwords of length n equals n + k for all n sufficiently large. The word is called k -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most k . In the present paper we give a complete description of the class of bi-infinite words of stiffness k and show that the number of subwords of length n from this class has...

*-sturmian words and complexity

Izumi Nakashima, Jun-Ichi Tamura, Shin-Ichi Yasutomi (2003)

Journal de théorie des nombres de Bordeaux

Similarity:

We give analogs of the complexity p ( n ) and of Sturmian words which are called respectively the * -complexity p * ( n ) and * -Sturmian words. We show that the class of * -Sturmian words coincides with the class of words satisfying p * ( n ) ≤ n + 1 , and we determine the structure of * -Sturmian words. For a class of words satisfying p * ( n ) = n + 1 , we give a general formula and an upper bound for p ( n ) . Using this general formula, we give explicit formulae for p ( n ) for some words belonging to this class. In general, p ( n ) can take large...

Sturmian jungle (or garden?) on multiliteral alphabets

L'ubomíra Balková, Edita Pelantová, Štěpán Starosta (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

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...